Blogbrother PISSED emails me about a neat anonymous search engine, ixquick. It anonymizes your searches so that prying eyes can't recover it. They also have an anonymous proxy service which is particularly interesting when you think about Internet telephony.
You can use either the generic service which queries the top search engines, or use their StartPage® option which uses Google's results. However, unlike Google it doesn't track your IP and strips all identifying info from the query.