Coloring is a very special thing indeed. Everyone can find a tut on the net but in the end, what makes the difference? Your own way to use what you know about colors.
Maybe I could start with a grey, then paint lights and shadows, and then colorize it. It's the super effective, quick technique of many digital concept artists. I do not paint like this at this time.
I use only colors; with different opacities, and take new mixed colors with eyedropper. I work for long on every single new element and make numerous modifications as the painting takes a form.

Yeah. It is very long.^^
But it's my way to appreciate, imagine and reprensent each details of the little world I'm painting. I think It's the most important when you work on an illustrated map. Of course, the final result must be precise. But during the process I think you need you map to be "living", even if it implies many changes...

I can't give other advices now. But if you ask, yes, i'll try to write a tut about the map. as I still have to translate my first tut into english. Because I also make satellite-like maps. ^^