CSS3のtransitionを使うとJavaScriptを使わなくてもアニメーションの指定が可能になります。
IE9以前は非対応です。
スクリプトとサンプル
#nav li a{
border-right:1px solid #fffdfb;
display:block;
margin: 0;
padding:0.7em 0;
text-align:center;
width:128px;
-webkit-transition:1s;
-moz-transition:1s;
-o-transition:1s;
-ms-transition:1s;
background:#42210b;
}
#nav li a:hover{background:#000;}