It's important to have downloaded the above mentioned tools and updates beforehand, since you will want to disconnect the infected computer from any network or Internet connection before attempting the following procedure.
Having got all these tools downloaded, you should load up Autoruns on the affected computer, enable all the "Show" options in the View menu and also enable "Hide signed Microsoft entries", then hit Refresh and attempt to identify any suspicious looking files that are being loaded on startup. These include executable files with random names, files that are marked as being from a search company or an internet optimiser company, and executable files that are located in Application Data or temporary folders. Use Autoruns to remove these from startup, then reboot the computer.
Run a scan with RootkitRevealer. This should reveal malware that is actively hiding its presence, including the Sony BMG malware and the various trojans that piggyback on top of it. More information can be found at Sysinternals.com. Sophos have released a tool to clean this malware from your system, which you can download at Sophos.com. Symantec have also released a removal tool, available at Symantec.com.
The next step is to install Ad-Aware. Load up Ad-aware, click Scan Now, select "full system scan" and start it off scanning. You will almost certainly find that you have to run Ad-Aware several times; if it has trouble quarantining/deleting affected files, try getting rid of them in stages, for example let it scan until it finds 100 items, then hit Cancel and get it to quarantine and delete those, then do it again, and so on. If Ad-Aware finds any processes or modules running that it doesn't like, you should try rebooting into Safe Mode and rerunning the Ad-Aware scan (to get into Safe Mode, hit F8 before the "Microsoft Windows" startup logo screen appears, then select Safe Mode from the menu that appears). Hopefully the previous step with Autoruns will eliminate most of these but often some of them slip through.
Once you are happy with the state of Ad-Aware's scans, the next step is to install Spybot. Once again, at the end of the installation, uncheck "run SpybotSD.exe" and instead run the two update files that you downloaded earlier. Then load Spybot and do a scan. As with Ad-Aware you may find that a reboot is needed to get rid of certain items.
Having finished with those two, we move on to the more specific antispyware tools CWShredder and ToolbarCOP. CWShredder is specifically designed to get rid of CoolWebSearch spyware, just run it and it will check your system for CWS and get rid of it for you. ToolbarCOP lets you check what Browser Helper Objects and toolbars and things you have in IE, and get rid of malignant ones such as WhenUSearch, MyWebSearch, 180Solutions, etcetera. After using CWShredder and ToolbarCOP you should reboot.
Now install AVG Free Edition, and during the installation process it will allow you to check for updates, if you downloaded the update files earlier you can instruct it to find the updates in a folder and it will let you browse to the location of the files. Having installed and updated it, set it off on doing a full scan of the computer.
After AVG is done scanning, reboot again and run Stinger, this should hopefully mop up any last bits and bobs.
In the event that there's still spyware or viruses on the system after doing all that lot, run HijackThis and send me the log file it creates.