
It is a universal truth that all search engines, including Yahoo, Google and MSN, retain search data of their users which can easily give a clue about the person's identity and a glimpse into his mind and online activity.
Though it is highly unlikely that Google users will ever come across this "AOL Data Spill" like embarrassing situation, the possibility cannot be ruled out completely especially after Eric Schmidt's remark that ".. this sort of thing would not happen at Google although you can never say never."
If you are worried that some day Google, by mistake, might disclose your private search terms into public internet domain, try some of the following suggestion that may fool the search engine or give it a hard time recognizing you.
The background is that when you perform a search on Google, the site search logs keep a record of your computer IP address, cookie ID and the search query terms. Google may also track your clicks on the search results by rewriting the destination URL. So we will look at possible ways to manipulate each of this information:
1. Disallow Google to Store Cookies - The important thing is that it doesn't suffice blocking cookies from just google.com domain, you must also block cookies from google site in your country.
For example, in India, one would block google.com and google.co.in - This is because Google redirects you to your local country page when you type in google.com in the browser address bar.
To block cookies, open the Cookie blocking dialog in your browser, type the site url and click disallow or block.
IE: Click Tools->Internet Options->Privacy->Sites
Firefox: Click Tool->Options->Privacy->Cookies->Exceptions
Remember that Google Personalized Search History won't work after you disable cookies from Google.com. Also, you may have to type the user name and password of other Google services like each time you have to login since cookies are disabled and you won't be automatically logged in.

Scandoo interace remains invisible to the end user and one would feel that he is searching via Google itself. [Scandoo Google, Scandoo IE Toolbar]

HideMyIP conceals your real IP address and shows a fake IP with a hostname to the sites that you visit. You can set Hide-My-IP to change your IP address every minute. [Download Hide-My-IP.com]

5. Block cookies from Yahoo, Google and MSN. Then use Dogpile.com for searching these three search engines simultaneously. [Dogpile Search]
6. Block Google from Tracking Your Clicks
7. Don't use Google or Yahoo to search the web as they will store your entire trail of activity on their servers. Try Clusty.com or Ixquick.com which do not save users search data. Clusty is a meta search engine based on Vivisimo clustered search - It queries several top search engines, combines the results, and generates an ordered list based on comparative ranking.
8. Finally, you can try Scroogle Google Scraper, a search wrapper around Google (and yahoo) search that lets you anonymously search Google and promises not maintaining your search query terms. [Google Scroogle]