Well since spyware doesn't really harm your computer (even though it can be really annoying, violate privacy, send information behind your back, and show you pop-up ads), virus scanners don't detect it currently. You should be careful what you install -- P2P apps (including the extremely popular "Kazaa"), "performance boost" apps, and other things people would think are nifty like toolbars, smilys for Outlook and so on often come with spyware. It's become a pretty big problem in the last year or so and it's gonna get worse before it gets better.
As far as getting rid of the stuff, I kinda prefer
Spybot: Search & Destroy to Ad-aware. You might also want to try that...
Anyway, for a search bar that's actually
useful, you might like the
Google Toolbar for Internet Explorer. Not only does it give you convenient access to a Google search, but it blocks pop-ups (and is free)! Has some other options too. (
Screen shot)