Are you using WPF or Silverlight?
If you are using WPF, it’s easiest to data-bind the appearance of the link shape (Path.Stroke) based on the value of UIElement.IsMouseOver. Or you can set up a Trigger to modify one or more properties.
If you are using Silverlight, it’s easiest to implement MouseEnter and MouseLeave event handlers to do the same kind of thing.
The more general mouse-over solution in Silverlight and in WPF v4 is to use the Visual State Manager. However, that would require re-implementing your link template to use a control as the link shape, which isn’t practical or efficient.