For recovery:
If you have file backups and a recovery disc then I would do a clean install. Some viruses and malware can hide from security software in the registry so it's probably the only way to be sure you're clean.
For the future:
The free security software mentioned (AVG, MSE, etc.) are...