Search Engine Watch has written a howto on privacy in relation to search engines. As part of the conclusion they write:
As you can see, ensuring your search privacy is tricky. The information you send is leaving traces in multiple places. The solution to ensuring privacy isn’t going to be as easy as passing a law that targets Google, Yahoo and the others. Ideally, the entire lifecycle of a search beyond the computer desktop needs to be considered from ISP through to tracking services. Searchers themselves also need to consider what they do on their own computer desktops.