Si tratta dell "Transizioni" CSS3.

In pratica tu continui a impostare lo stato normale dei links e lo stato hover mediante la psudo-classe :hover, come hai sempre fatto.

L'unica aggiunta è quella di inserire alcune regole in più nella definizione dell'aspetto dei links, quelle relative appunto alle "transizioni". In teoria basterebbe una regola sola, ma al momento devi ancora usare i prefissi per i vari browsers:

codice:
transition: all 1s;
-webkit-transition: all 1s; /* Safari */
e altre simili per gli altri browser..... così facendo la transizione da uno stato all'altro non sarà immediata ma durerà 1s (come specificato dalle regole)