Boot into safe mode and install (and run) an anti-virus program. I use Bit Defender because its free, and would personally go with a free version first, just because they do less with thier installs.
While you are there, here is my list for total Windows security-
1. Install a software firewall, preferably one which monitors both incoming AND outgoing traffic. My recommendations are ZoneAlarm and Sygate (both have very good free versions).
2. Install (and run) anti-spyware programs. I recommend three total- AdAware, Spybot SD, and SpywareBlaster.
* make sure you update the software to the latest version.
3. Install anti-virus software. I prefer something with on-access monitoring, but I havent found a free version I like which has that function.
* make sure you update the software to the latest version, with the latest virus detection files
Also, make sure you have some sort of pop-up blocker. WinXP SP2 has one built in, so you will want to upgrade to that if you havent. If you are on Win2000 and below, install Google Toolbar, it has a good popup blocker.
After you run (from Safe Mode) the virus scanner and it clears out as much junk as it can, try installing and running the anti-spyware stuff as well. Then reboot, and run the personal firewall; this will stop any remaining junk from accessing the internet (you may have to do this from safe mode as well if it locks up the computer, but it usually will not, since you should have already cleared a lot).
Once you are able to boot into Windows normally, make sure you can access the internet. If so, update all your new programs (virus scanner and spyware detectors), and rerun them. Make sure you run these one at a time, dont know if I needed to say that.
Make a list of all the programs trying to access the internet which the firewall is blocking. Check their names out on Google; most of them will probably be some sort of virus; if your program(s) didnt catch them, there are usually directions on how to remove.