quello che normalmente scrivi nel tag style lo metti in un file con estensione .css e lo ricchimi con <link rel='stylesheet' href='stile.css' type='text/css'>

forse non va perche il link e sottolineato di suo, e con a:hover{text-decoration: underline} non succede niente