If you are concerned about giving away too much of your private information to one of the top Web-search engines (Google, Yahoo Search, Live Search, Ask.com), then you can use the following method to protect your privacy without compromising on the quality of search results. It's crucial that any solution to the privacy issue be uncompromising with not only the quality / relevance of the search results, but also with the quality of search experience, although slight compromise with the latter is an acceptable price to pay to get increased privacy.
It must also be remembered that the solution outlined here is only 1 of the several easy-to-use measures that can be used to protect your privacy when conducting Web searches.
For Google users: Use AOL Search. It provides the high-quality search results of Google without directly letting Google associate any of the searches with you. To make it less painful to access AOL Search, set it as your homepage, bookmark it, add it to the search box of your favorite browser and set it as the default search engine, and so on.
For Yahoo Search users: Since I'm generally logged in to Google, and not Yahoo, I find it OK to search directly on Yahoo Search. If however, you do not wish to search on Yahoo Search, use Forestle. It provides Yahoo's results while keeping you anonymous. Engines such as AltaVista and AllTheWeb do not protect your privacy, as they use a Yahoo.com cookie.
Fore Live Search users: No great alternative, although Search and Give is a fine one (if you are not signed in). I use Live Search directly, since I am never logged in to any Microsoft website, and hence all searches I conduct on Live Search are anonymous by default.
For Ask.com users: For all practical purposes, you are already anonymous. No need to look elsewhere.
As an alternative to the above, you may use one of the better metasearch engines. I prefer Ixquick, although you may also choose from Scour, Dogpile and Clusty (in decreasing order of preference). Don't even look at the the dozens more metasearch engines that are completely trash-worthy.
As a side note, there are other search engines that are based on one of top 4 search engines (such as Click4Carbon, GoodSearch, Lycos, etc.), I do not recommend these because they have poorly-designed or slow user interfaces which mar the search experience unacceptably.
My Idea For An Advertising Campaign