The HTML/CSS default for links is underlined, so unless your template (like the stock template) specifically changes this, it will happen even when there is no mention of underlining.

Add to this rule in stylesheet_footer_menu.css


#footer li a:link {color: #f00;font-size:11px;margin:0;padding-left:1em;padding-bottom:.3em;line-height:14px;display:block;text-decoration: none;}