It startles me sometimes just how paranoid computers have made us. I've some got stories! Personally, I think privacy concerns often get overblown. But on the other hand, some concerns are legitimate.
When it comes to online privacy (including search engine data), you might give
Tor and
Torpark a whirl. Or you can just program
proxies into your webbrowser. The use of proxies should adequately anonymize your searches.
Far and away though, the biggest 'computer' threat to your privacy is out of your hands: business and gov't databases. Whether it's lost gov't laptops with sensitive data, or a small business owner who has no clue for securing client data, these databases put you at most risk.
One thing you can do to help insure your privacy is clearing spyware and viruses from your PC. Compromising PC's is big business.