Actually, whether links should be underlined or not depends on the context.
In menus and the like, they generally shouldn't be underlined as people expect the text to be clickable anyways - the links should be underlined when hovered, though.
Apart from that, links should pretty much always be underlined, yes.
