The Electronic Frontier Foundation has published a terrific, concise guide on how to avoid the fate of AOL Searcher No. 4417749 and countless others:
How can you help prevent damaging privacy invasions like AOL's data leak? Along with spreading the word about this debacle, you can take steps to protect yourself online. (...) [W]e've listed some tips and tools that will help keep your search history private.Continued here. (thanks, Cyrus Farivar)
- Don't put personally-identifying information in your searches, at least not in a way that can be associated with your other searches. You should take the precautions below to avoid giving away your identity to your search engine anyway, but they're especially necessary if you want to do a search to see if your personal information has appeared online or want to do a vanity search for your name.
- Don't use a search engine operated by your ISP. Most ISPs inherently know who their users are, at any given time and over the long run. If you use their default search tool, they know who you are and everything you search for. Use someone else's search tool instead.