Buenas,
1) Para eso (si solo entras a nivel de provincia no necesitas ajax). Lo que tienes que manejar son arrays relativamente pequeños con lo que montandolos de forma literal...
Código:
españa.andalucia=["almeria","granada","malaga","cadiz",... ]
...te debería bastar.
2) Puedes montar tu mapa con imagenes y jugar con las coordenadas para saber donde está el ratón pero te aviso de que va a ser un trabajo de chinos delimitar con HTML las coordenadas de cada comunidad autonoma en el mapa.
3) Luego deberás lanzar una función que cree un div con posicion absoluta y con el css que te de la gana.
Vamos que si no sabes DHTML lo tienes chunguillo y si sabes pues tienes trabajo por delante.
4) Otra solución que para este caso creo yo que te iría mejor sería maquetar todo el mapa en flahs donde la definición de objetos vectoriales es más facil de hacer.