I just noticed the main Google page now has autocompletion for the search box:
The feature, called Google Suggest, has been in the Labs for awhile. It "graduated" to the main front page almost exactly one week ago.
This is going to make it easy and lots of fun to check the most popular search term for a particular topic!
Yahoo, youtube, and ebay are suggesting as you type too!