I don't know if that's true. Most web hosting companies have started advertising on the parked domains or domains that have not yet been hosted. Perhaps a link to that domain is placed in one of their pages that search engines index.

Google has "Adsense" or something like that for parked domains. Perhaps domain registrants are pinging google to encourage them to publish ad sense ? I don't have a clue on this one.

I just registered a domain and I have no link to it anywhere, not using Google toolbar or anything the like. However, I can find it already using google. It seems there is no other way they could have found it unless they get a list of newly registered domains from the providers or they actually try random string values as domain names.

The answer is most likely DNS. All domain names are sent to DNS servers around the globe, at ISP's everywhere.
All Google has to do is compare its current list to an updated list, and it then knows of new domains. Anyone with a DNS server can do this.

building a website....got a domian and do not know what to do from here...seeking assistance on what steps to take to find out what i do with the domani and how do i find it..in order to get the websiet for my new business up and running?

Google, Yahoo, Alexa and all the other SE's compare their SE index to what is already on the web... Then they run their "robots" to see if anything changed...
That is how the SE';s find out new registered domains

With all do respect these bot can also look at the verisign data and determine which have been just registered. Look at registeredlookup.com The bots know by the data and if the whois information changes.