Although the use of spyware has exploded over the last year or two, most people do not realize how easy it is to remove. Most of the crap that installs can be easily deleted. A few installers are covert, but most of them specifically ask users for permission to install. Using a bit of good sense, like in other areas, can cure most ailments before they begin.
The first step is learning the obvious. Go to control panel, add/remove programs, and uninstall the spyware you find there, if any. If you don't know what a program does, do a quick search on Google.
However, as I said, some of them are subtle. These programs are excellent at removing the more elusive ones, that install covertly.
If you aren't running a anti-virus program, shame on you. Not only are you leaving yourself wide open, you are also threatening others through your negligence. Norton 2004 is an excellent anti-virus program, and contains an added bonus new to the 2004 edition: basic anti-spyware detection.
Your second line of defense. A free download, with regular updates for common threats. It prevents some spyware by refusing the ability for known bad entries associated with malware or spyware to be added to the registry.
Purely and efficiently designed for one purpose: to eradicate spyware and malware that has been installed on your computer. Your most valuable tool in detecting and removing the naughty programs.
Spybot Search and Destroy
A lesser but still useful program, of the same type as Ad-Aware. Since the companies do not share their definitions, they will each find some things the other won't. If you don't mind the extra effort, it is good to have this as a backup for Ad-Aware.
Ferrets out orphaned registry entries. After running all the above programs, run this to ensure you have removed all of the problem apps.
Another program used to clean out the registry - like before, it is wise to have a backup, because every program detects different items.
If you take a few minutes to set up these programs, update them frequently, and run them every couple weeks, you probably won't have any problems to speak of. I have yet to encounter a bit of spyware that can resist all these attacks. If you can find one that does, let me know, and I'll update with newer or more sophisticated ideas. Best of all, all these programs except Norton AV are free, so knock yourself out!