Remember this… Scan-Reboot-Scan. Malware can sometimes repair itself unless this repetition is performed.
4.1 Assuming you have existing anti-virus software installed you should initiate a full computer scan. This may take a while but it may find things it can clean. That being said, is is typically unlikely that anything is found as one would assume that the existing anti-virus software should never have let the malware run in the first place. It is also possible that updating the anti-virus signatures will provide more up to date protection that may then actually deal with the malware.
4.2 This is where it gets more interesting (more complicated).
A list of anti-virus software can be found here and instructions on how to download them and guidance on how to use them. It is still advisable to keep the infected computer disconnected from the Internet. Use a second computer and copy anti-virus software to a USB, CD or DVD device and copy them to the infected computer.
IMPORTANT NOTE : While USB drives are convenient you should note that it is possible for malware to infect the USB device when plugged into the infected computer. You should assume this might happen and for this reason a CD or DVD is preferable as it can be burned so that the infected computer cannot infect it and spread to other computers.
Step 4.2 is known as the Scan-Reboot-Scan phase. It is important to Scan with all possible anti-virus software available, Reboot to ensure any malware is flushed out of memory and Scan, to see if any initial detection now comes up clean.
4.3 Was anything found ? Repeat the Scan-Reboot-Scan process until no detections come up.
4.4 When no threats are detected it is now time to run final checks via online scanning services. The benefit of these services is that the signatures they use are as new as possible. Re-connect the computer to the Internet.
A list of online anti-virus scanning services can be found here.
These should only be used to verify that you have dealt with the malware. Remember, connecting to the Internet risks data loss or further infection.
4.5 If anything was found use repeat the Scan-Reboot-Scan process using the online scanners.