General
Some spyware/adware infestations are so bad that you need to boot into safe mode (by pressing F8 at boot-time) and run Ad-aware, Spybot Search and Destroy and MS Antispyware multiple times until each runs once and detects nothing.

MS Internet Explorer
Internet Explorer Options.  I change the Security Zones in IE.  I disable everything in the Restricted Zone (use the advanced tab) and also turn down the Temporary Internet Files settings for storage.  The Content Advisor is worthless, in my opinion.

Google Toolbar
http://toolbar.google.com I have used this from 1/5/04 to the present (8/2005).  This is a must.  Some websites are starting to get around it, but it does block most popups for free.  To use the advanced features, you must send anonymous data to Google.  Based on their privacy policy, I allowed this with no negative repercussions.  Update 3/2005 - they have a new version (beta 3.0.120.7 to be exact) with spell check and a very nice map feature.

Ad-Aware
http://www.lavasoftusa.com/software/adaware/ This is free.  I have used this to remove "HotBar" with great success.  The user interface is very nice and easy to understand.  Run an update each time you use it.  You can customize it to your needs.  In my opinion it is conservative in its approach and won't do anything to your system unless you specifically tell it to.

Java Cool Software
Two little applications from http://www.javacoolsoftware.com seem to be regarded highly, so I started using them. I started using them on 5/3/04, no problems so far (as of 6/3/04). I will post any problems with this. I have used them to block spyware installation and they do work.
SpyWare Blaster - http://www.javacoolsoftware.com/spywareblaster.html This does not run in the background, it does block installation ActiveX controls, browser hijackers and some others. It does need manual updating - but they have an update service ($10 per year) to automate this (I have not tried it). I am just updating manually. This is added to my monthly recurring maintenance tasks (you have one of these, right?).
SpyWare Guard http://www.javacoolsoftware.com/spywareguard.html This builds on Spyware Blaster's protection. It does run in the background. Must be updated manually - they have no Auto Update service for this one.

SpyBot Search and Destroy
http://www.safer-networking.org/  This is free.  I use this with Ad-Aware.  They do work together and I have been very pleased.  It can get very aggressive if you want it to.  I have taken all their recommendations with no problems.  It has a "Tea Timer" which monitors processes and stops known malicious ones.  It also guards your some critical registry keys.

Microsoft Antispyware
http://www.microsoft.com/athome/security/spyware/software/default.mspx  This is becoming useful as Ad-Aware and SpyBot do not catch everything.

D.I.E.S.C.U.M. [TM]
If you have a severe spyware infestation which cannot be removed by Ad-Aware, SpyBot or MSAS, then you need to follow the D.I.E.S.C.U.M.[TM] procedure. I have never had to do this, but this is highly regarded by a number of professionals. This is from Carl Houseman of Sunbelt Software's NTSYSADMIN newsgroup (see my newsgroup section for links). Hint: set aside a few hours. http://www.santeriasys.net/article2.html

Host file manipulation
I have done this for years. This can turn into a nightmare to maintain. It is very effective. This works by "lying" to your computer. You tell it that an advertiser's website is actually on your computer, and nothing displays. I quit doing this because of the maintenance. Google it and you will see lots of info. Here is one http://accs-net.com/hosts/get_hosts.html

ZoneLabs
I have not tried their latest spy/adware software.

FireFox - http://www.mozilla.org/This is a popular alternative to MS Internet Explorer.  I have used it occasionally, it seems pretty nice.  It does need periodic patching, just like MS Internet Explorer, but I there is no way to centralize this.  Update 8/2005 I think they have solved this problem, I have not looked.  Just remember to keep up on patching Firefox, if you decide to use it.

Proximitron
The GRC newsgroups rank this high, I have not tried it. Sorry, no link.

BOCLEAN
http://www.nsclean.com/ This used to be the standard to remove malware. (Back Orifice was the original purpose of this). That was pre 2000 and it seems to be completely different now. I have not tried it. The GRC newsgroups regulars seem to like it.

Windows Registry Concealment
As of 8/25/05, most spyware scanners will not detect this.   http://isc.sans.org/diary.php?date=2005-08-24 "An overly long registry entry can be added, but won't be shown by regedit and regedt32. Even better, all registry entries that get added afterward under the same key, even if not overly long, will be hidden as well."

McAfee (anything)
Bad experiences abound.  No good experiences in my boat.  I am done with McAfee.  If you have McAfee software and your computer is broken, format the hard drive.  Sorry, but that's how I feel.  McAfee antivirus has been given away by Dell in the past.  In my opinion, zero dollars is what it is worth.  It has caused me at least 3 catastrophic system failures in the past.  Antivirus software is a necessity.  Budget $20-$50 per year for each computer.  Update 08/2005 - The latest products seem to less of a let down than in the past.  I got a free trial and used it for 2 hours and then replaced it with AVG 7.  Oh well.

Evidence Eliminator
I have been spammed by these scumbags and refuse to purchase their products.  They use FUD (Fear, Uncertainty and Doubt) to push their (ahem) **products** onto innocent PC users.  I ran across this website - http://ee-sucks.tripod.com/ and its' claims are supported, in my opinion.  See some threads on the GRC newsgroups from July 2003.