Código:
.menu a:link{text-decoration: underline; color: #000;}
.menu a:visited{text-decoration: underline; color: #666;}
.menu a:hover{text-decoration: none; color: #036;}
.menu a:active{text-decoration: none; color: #FFF;}
.menu es la clase, si lo deseas para todos los links de la pagina elimina
.menu de cada declaración.
Espero que esto te ayude.