Ich habe es hier mit den Links in der Navigation so gemacht: http://mannithedark.ma.funpic.de/Designs/5/
Du musst nur zB einen span in den Link reinpacken, der beim drüberfahren sichtbar wird:
HTML-Code: 
<a href="#" class="tooltiplink">
Der Link
<span class="tooltip">Dein Tooltip <b>auch mit HTML</b>!!!</span>
</a>
Das passende CSS:
HTML-Code: 
span.tooltip {
  display: none;
  border: 1px solid #000000;
  background: #FFFFFF;
  font-size: 12px;
  font-family: Verdana, sans-serif;
  color: #1F1F1F;
}

a.tooltiplink:hover span.tooltip {
  display: block;
}
Ist ungetestet, sollte aber klappen...