It doesn't necessarily have to be malware related. A lot of sites have scripts from advertising brokers that set cookies, and the latest fad with sites seems to be trying to get detailed breakdowns of site visitors. Operating system, browser, browser version, etc, which can be easily gotten from any web browser if you know how.
What works really well for me, is using Mozilla Firefox. I can tell it to ask me whether or not to allow every single cookie request, and then I can either allow or deny it, which the browser will then use to create a white and blacklist of domains. So I can tell it to block all cookie requests from www.badsite.com but still allow them from www.goodsite.com. It's another little perk on top of the improved security over Internet Explorer for using Firefox. Another option is to tell Firefox to simply delete all cookies every time you close it.
But the best way to prevent malware and viruses is by adhering to the following guidelines. These are only suggestions, but the more you follow the better your odds of avoiding problems will be.
1) Avoid using Internet Explorer as much as possible
1a) Use Mozilla Firefox, Seamonkey, Safari, or Opera
2) Be sure to always install security updates for Windows
2a) One and only time it's safe to ignore #1
3) Firewalls are important
3a) XP's firewall is good enough, but feel free to use a third party one
4) Anti-Virus programs are important
4a) If you need a free AV program, try AVG Free and Avast
5) Avoid using any pirated programs
6) Avoid using any file sharing (P2P) programs
7) Avoid using Outlook or Outlook Express
7a) I would recommend Mozilla Thunderbird or web based email such as Gmail
How do viruses and spyware add cookies? There are sites I haven't visited listed in my cookies... And how do I prevent it?

Chowhound
Comic Vine
GameFAQs
GameSpot
Giant Bomb
TechRepublic