eso se hace con CSS (hojas de estilo) por ejemplo de esta forma:
/**************************************/
a:link, a:visited {
color: #990000;
text-decoration: none;}
A:hover {
color: #FF0000;
text-decoration: none}
/**************************************/
El "text-decoration" es el que determina el subrayado y puede ser:
none= ninguna
underline= la clásica linea de subrayado
overline= una linea por arriba del texto
line-
through= tachado
blink= parpadiante
si queres saber más pasate por el foro de CSS
