You might be able to prevent privacy invasions like AOL’s data leak with a little bit of understanding and tweaking.  Already Firefox has an extension that makes it hard for anyone to retrace your search pattern.  In the meantime, you can take steps to protect yourself online.

An obvious one is to not put personal identifying information in your searches.

Don’t use a search engine operated by your ISP because they will know who you are.

Don’t create or log in to a search engine account. If you have to because of your GMail account or Yahoo! Mail, make sure you remove your cookies.

Don’t accept cookies from your search engine. Don’t let the personally-identifying information in your e-mail get linked with your searches. Firefox users can use the free CustomizeGoogle extension to anonymize your search cookie without breaking GMail.  As of yet, there are none for Yahoo!, MSN, and AOL users.

Use a separate browser or browser profile for search and for other activities.  This is one of the easiest thing to do.  For instance, I use Firefox for my main browsing but use Camino for searches.

Use an anonymizing proxy, or proxy network like Tor, to prevent search engines from learning your IP address, especially if your ISP gives you the same IP address each time you use the Internet.

The EFF website has plenty more on this throny subject.