On Kindle 2, to remove the underline from a hyperlinked word, try the following:
A word in this <a href="http://www.google.com"><font color="white" size="0">.</font></a>sentence is linked.
I actually have an even better way of doing this that I devised, but I'm jealous to give out how :P
I literally spent 10 hours researching the net and testing this myself (MOBI file format, not sure about the capabilities of ePub). Text-decoration and all that jazz just does not work on a hyperlink in a MOBI file. There's almost no information on this that can be found via Google.
My specific use is hyperlinking words to a glossary in the back of a book. If anyone else needs to do this and is interested in removing the underlines from the words, let me know.