Devi crearti dei layer (livelli) di tutte le regioni, uno per regione da sovrapporre all'immagine della cartina geografica.

Puoi usare anche un colore neutro nella creazione dei layer da sostituirlo al momento della visualizzazione.

Fai tutto con le librerie GD di PHP.

http://php.net/manual/en/book.image.php