How to create colored World maps? I would like my users to be able to select the countries they have visited and then highlight those countries on a world map.

I've come across a few commercial flash solutions with XML config files but would rather like to avoid flash and have jpgs or pngs generated.

This site is a good example of what it should look like.
You can probably use OpenLayers, with MapBox to create custom map layers with MapBox.com