Google is adding a feature that brings up suggested searches as you type, Google Suggest, as default on Google.com in the coming weeks. Google Suggest has been working on this feature for years, and it has been available to users in Google Labs.
Google has already added Suggest to the toolbar and YouTube.
Yahoo, Live.com, and Ask.com already offer search suggestions.
Like many updates and features, expect it to be rolled out to a few users first and then more and more as the days pass.