No need to fear for your life or anything, but it’s always nice to know that everyone who uses Google has a cookie that expires 2038. The cookie is not edible, but it will track your use on the site and log your entire search history. Google has allegedly indicated that they won’t be deleting user’s search histories. This doesn’t really bother me, because they can do whatever they like as long as it says so in their terms of service. Google has obtained many useful tools online and some would rather give up their privacy than give up using google. There is nothing wrong with that. Other set up proxies which are a pain to set up for newbies and make websurfing slower. Websites like one I found via gHacks can be used to bypass direct search snooping.
The best solution that I am using is going through Blingo which offers prizes for using Google through their site. Here’s an invite to Blingo which will allow you to win prizes for signing up. Without registering, they cannot send you anything without an address. Otherwise, you can still use blingo to anonymize your searching habits because Google has no way to access your account through blingo. After signing up, you can make things even more convenient by installing a specific Blingo firefox search. I like using the search bar in firefox and adding the extra searches because it has almost all popular search engines I need and even popular sites that have aren’t search-based.
Another sure solution is to ditch Google altogether. You can use alternative search engines like AltaVista, Yahoo, MSN, or whoever. Most of the searches are equal in quality, but the order I listed them in are akin to my preferences if I were to avoid searching on Google.