Simples! Você vai precisar desses dois códigos Javascript: jQuery e MapTips (versão minimizada). Você também pode querer o CSS base para formatar as MapTips.
Após chamar os dois arquivos em sua página, veja o código fonte do exemplo 1 acima. São necessárias apenas duas linhas de código! (as linhas novas possuem um comentário "MapTips aqui!")
O método add_tooltip deverá ser chamado para cada marcador que terá uma tooltip.
O código foi testado em Firefox 3, Opera 9, Internet Explorer 6 e 7.
Página do projeto MapTips no Google Code.