Anonymize your Google searches with the GoogleSharing add-on for Firefox
GoogleSharing is an experimental Firefox add-on which selectively routes Google searches through an anonymizing proxy. Searches remain very snappy -- and Google is none the wiser.
GoogleSharing is very selective, and anonymizes only your search traffic. GMail, Google Reader, and other such services keep working normally since you don't have to be logged out of Google for it to work.
One side effect worth noting: by default you'll get results from Google.com itself in English, and not from a country-specific Google domain (like, say, google.co.il).
GoogleSharing is currently experimental, so you need to be logged on to addons.mozilla.org to install it. It also warned me about compatibility with my Firefox 3.6 but worked flawlessly anyway.