In your theme's style.css find the sidebar and footer elements (something like #footer). I'll use #footer for the following examples.
Look for #footer a { color:#something; and so on }. There may also be a #footer a:hover { color:#somethingelse; and so on }.
In the element #footer a:hover you need to add color:#CC0000; text-decoration:underline;. So, I have:
#footer a:hover {
color:#CC0000;
text-decoation: underline;
}
That would make a link look dark-red and underlined.
Without your site's URL and your exact color choice I can't give you exact code.