Tout d'abord voici l'image, un gif animé :
Ligne animée

Et voici le code CSS qui permettra d'avoir le lien survolé qui s'anime : 

a:link {
	color: green;
	white-space: nowrap;
	text-decoration: none;
}

a:visited {
	text-decoration: none;
	color: green;
}

a:hover {
	text-decoration: none;
	background-image: url(animated_line.gif);
	background-repeat: repeat-x;
	background-position: 100% 100%;
	padding-bottom: 0;
	color: navy;
}

a:active {
	text-decoration: none;
}

Et enfin un exemple concret.