I also feel like it's not necessary to underline non-hovered links, this makes everything underlined.
With the rules:
a
{
text-decoration: none;
}
a:hover
{
text-decoration: underline;
}
it looks like this: http://i.imgur.com/reqSIva.png
