Okay... here's how to do it. If you've got Windows XP - if not, stop reading.
Go to your Windows/System32 folder.
Then view the files by detail.
Then order the files according to the date created (you should be able to add this option by right-clicking next to Date Modified in the sub-menu in the window).
Now... look for any applications (.exe) or application extensions (.dll) that have been created on your PC on dates where you didn't download anything.
Make a note of the earliest date....
Then go to Start -> Run
and type in msconfig.
This will bring up a window. There should be an option to restore your PC back to a date. Restore your PC to a date before the earliest date any of your dodgy spyware stuff was downloaded.
And then you should be okay.
You should also Google Hijack This and then download it.
Em... got to run. But if you do download Hijack This, post up the results of the search here and we'll see what to do (that's if the msconfig thing doesn't work).