Try searching for "image map css rollover". There are a number of examples where people have created image maps from definition lists or divs so that they could build in rollovers. The same logic they used for rollovers could be used for static content, or if your using server-side coding (like ASP) and don't plan on using an AJAXy method to keep the map updated, you could generate the map statically as a bunch of divs and cause it to display the towns in red or green by just placing a different CSS class on the div for that town.
I think the div plan would be easiest. Basically have one container div with CSS to set the width, height, background image (your state), and position relative. Then have a list of your cities with coordinates and output each one as a div with a CSS class based on their state (good, problem). Those classes could have two different images for the city icon. An anchor tag with display set to block could probably work just as well and give you the linking capability you want.
If you want to go the route of client-side updates, then the only data you need after you initially build the map is an array of cities and their status for any items that have changed. Position wouldn't be necessary, as towns don't up and walk around very often.
Working out the coordinates may be a little rough. One option would be to get the coordinates of the towns in longitude and latitude. Convert those values to decimal, then map them to the div coordinates using the long/lat of the top left of the map and the width/height in long/lat of the map. Once you have the dimensions of your map in long/lat and you know them in pixels, mapping the long/lat values of the towns is just a very quick calculation.
Let us know if you need more ideas and definitely post back with some info on how it's going. this sounds real interesting, wish I had time to work on something similar
-T
