I've just spent 8hrs cleaning up someone elses machine, 98% CPU power take up by exe/dialers/spyware - some of it so deep it took an age to find it all - several of the exe's looking for each other and if one was missing the spawned new ones - bastards.

I recommend:
Norton Anti-Virus - Keeps you up to date but wont clean up spyware.
Ad-aware - good but not that good at getting the deep stuff out.
Spybot - Very good at getting the nasty shite out.
Zone-Alarm - A royal pain to start with but once you teach it what's safe it really does work wonders. When I switched the firewall on, the machine was attacked with 2 mins of going on the net.

You can get all the above from Tucows...