I just did similar today but to remove underlines on links. In my style.css I opened it and searched for a:link. I changed it to none and saved it. This should work to change yours to underline as.
In your case Search the file for a:link, a few lines below it you will see tex-decoration: none; change none to underline;
I just wanted to chime in because I wanted to point out something that I didn't think of. At first I was getting frustrated because when I refreshed my page the underline was still there.
I'm running the W3 Total Catch Plugin (by the way I highly recommend it for speeding up site load time). I went to the plugin settings and purged all cache. Went to my site and the no underline was visible.
As always save your original file to backup before making changes incase something breaks. :)