To change the default color and/or underlining of hyperlinks, you can alter the defined style of hyperlinks while composing a new message.
Type or insert your hyperlink like you would normally do.
Open the Styles and Formatting pane
Outlook 2003 with Word as the e-mail editor
Format-> Styles and Formatting…
Outlook 2007 and Outlook 2010
tab: Format Text-> click on the expand icon of the Styles group (see below snapshot #1) or simply use the keyboard shortcut;
CTRL+SHIFT+ALT+S
Right click on the Hyperlink entry in the Styles and Formatting pane and choose Modify…
Modify the default Hyperlink style.
Change the font settings for your hyperlink.
For instance, remove the underline, enable bold and change the color to green. You may format the hyperlink in the message composer and select Update to match selection
as snapshot #2 below
To change it for all new messages that you create Outlook 2003 with Word as the e-mail editor Enable the option: Add to template
Outlook 2007 and Outlook 2010 Select the option: New documents based on this template
Apply modified Hyperlink to current and all new messages.
Press OK to apply the style changes and to close the dialog. Close the Styles pane via the close icon (X) in the top right corner.
Reference here form Microsoft.
Update
For visisted/followed link formation, go for FollowedHyperlink
(we go for Hyperlink
for the normal link formation)