Hola:
Si quieres hacerlo dinámicamente tendrás que ayudarte de algún lenguaje del servidor como php, y si quieres un ejemplo, échale un vistazo a esta página:
Creación de áreas en imágenes... en esa misma página puedes ver Madagascar con otro color (claro que como rollover)
Saludos
