How to add clouds or fog to an existing map in GIMP?

[Redrobes]

In a VTT we just add a token which is a semi transparent PNG with a tint. Like this...

In PS etc just add a layer, fill it with blue, white or orange and whack down the opacity.

[torstan]

In Gimp create a new layer above the map. Take a large fuzzy brush (size of 50 to 100 or more) and a very light blue. Paint in the regions you want to be misty. Don't be afraid to go too heavy, you can always lower the opacity of the layer to get back the map.