A thread at WebmasterWorld named Psychic Google? discusses Google's physic ability to locate newly registered domain names soon after they are registered. For example, if you buy a new domain name today, you might find the "coming soon" page in the index without you linking to it. I am of the belief that Google is finding it via a link from some page.
People are speculating that if you have the toolbar installed, Google can find new pages. I doubt they do that. And an other theory is the the domain name registrars are selling these names to Google. Come on!