Is there a rule that states that all links should be underlined to make them look like links? I have seen many sites where the footer, for example, does not have underlined links.
There's no rule, but it's good design to make your design act as users expect it to (and most users expect links in text to be underlined). So if you don't underline them, make sure the look obviously clickable. See: http://www.useit.com/alertbox/20040510.html
I personally can't stand links that aren't underlined in text (See: Stack Overflow). You shouldn't have to scrub the text see what's clickable.