Your best bet is to get ad-aware and spybot, make sure they're up to date. Also, GO DOWNLOAD MICROSOFT ANTI-SPYWARE! I've found it works better than the other two combined (personal experience, I'm sure your results my vary, not trying to start a flamewar on the topic).
Boot into safe mode (WITHOUT networking, if you have the option (XP, 2k). Do your scans there. this should pretty much clean you up. If not, you may have something pesky like VX2, which is a ROYAL PAIN IN THE ASS to get rid of. Here's a link for removal using Killbox and DLLCompare.
http://www.lavasoftsupport.com/index.php?showtopic=54511Also, if you don't want spyware DO NOT USE INTERNET EXPLORER. I was always of the opinion that with SP2 and a properly updated system, that there was no need for firefox, and that IE was the only browser I was gonna use. After getting hit by VX2 and CWS (cool web search, even harder than vx2 to get rid of...), I decided to try not using IE for a while, and switched to firefox. Now, I like firefox better, and I run scans daily, and since the switch I have had exactly 0 spyware infections. When I was using IE, almost every other scan would come up positive for spyware.
IE is very insecure, and it's the security holes that sites use to inject spyware.
--NipsMG