According to Udi Manber, VP of Engineering at Google, about 25% of the queries (searches) that Google processes today have never been searched for on Google before.

Isn’t that AMAZING! Long live the long tail…

ReadWriteWeb has a full writeup here.
Search Engine Land also does a good job of reporting this story here