I've been using startpage.com to search Google anonymously for the past year. Startpage proxies your query to google and back while leaving off the identifying metadata, making the query anonymous. At first you notice the slight increase in roundtrip time, but quickly get used to it. I find Google Search to have a better search engine than any alternative I've tried, so Startpage is right up my alley.