Virus

Hola
Últimamente cuando abro el navegador Internet Explroer me aparece una ventana que no entiendo muy bien lo que dice. Viene en ingles. Dice así:
Netwlork Administration Important Notice:
Your PC test Result: PC speed y PC privacy.
Attentio: Your computer es infected with spyware and adware. You can protected your privacy and improve your PC perfomance by removing spyware. Do you want to remove spyware in a few minute ?
No se si se trata de un virus grave ni de las consecuencias que puede tener y me interesa saberlo ya que es mi pc de trabajo.
Otra cosa. A veces navego por internet y como comparte el pc, no quisiera que quedara ningún rastro de los sitios que he visitado.
Después de navegar hago lo siguiente: entro en herramientas y en opciones de internet "ellimino archivos" "lugares visitados" y las cookies. Después me voy a la carpeta de windows y dentro de "favoritos" borro todos los enlaces que se han quedado grabados. ¿Hay algo más que deba hacer? Si algún día se mete alguien que entienda en el pc, ¿puede ver lo que he visitado? Muchas gracias