Matthew Fordahl writes about cleaning spyware, pop-ups, and adware from his brother-in-law's one year old computer.
Spy Sweeper and Ad-Aware had the most success of the programs I tested, with each reporting fewer and fewer problems after each scan. Though I was never able to run scans that came up with zero problems, the PC's behavior grew closer to normal. I also tried combining the two, and that helped rescue my home page.
One cool tool not mentioned in Fordahl's article is Autoruns. I used it the other day to help track down a few spyware start-up programs that Adaware missed on an infected PC.