The recent exposure of internet search data by AOL had led to lots of interesting discussions about security and privacy and about the fact that search histories frequently have enough information to identify the searcher.
One of my compatriots, Paul Madsooon, wrote about TrackMeNot -- a plug-in for Firefox which periodically issues random search queries in order to confuse and obfuscate the real search history of the user.
This type of solution (noise generation) can lead to performance problems and network overload (just imagine the load on popular search engines if everyone used such a tool all the time).
I think a better solution would be to use the great anti-royalty music-sharing P2P model to share the submission of search queries within a large P2P network. When I submitted a search query, a random partner in my P2P network (perhaps even indirected to a subsequent random partner) would be chosen and the search submitted to the search engine through that partner rather than directly from my system. Each query would be submitted through a different random partner.
This would eliminate the traceability while also keeping any one party in the network from building the same kind of data (which is an issue with the other potential solution -- using a proxy to combine multiple user's queries from a single source).