It doesn't really matter whether the tips are for photoshop or natural media if you plan to use photoshop or similar raster image creating software. The concept is basic: You're trying to create a 3-Dimensional area on a 2D surface. Just think of this type of map as a landscape painting viewed from a higher angle and somewhat condensed, and then paint accordingly.
You could start with a dark mid-tone and work toward the highlights as Felwynn is doing, for the most part, or start light and go dark like a watercolor... it's really just working preference. Strong lights with shadows pop forward, cool colors recede. Try to keep your color warmth pretty even throughout (if your light source is warm, your shadows are cool, plus or minus local color of objects, bounce light and reflective colors). It might help to start if you find a painting or landscape picture you like the color scheme of and pick your colors selectively from that for your brushstrokes. It also helps if you start with a loose sketch, whether a line sketch or a value sketch (paint it roughly in greyscale first then modify the layer with a hue adjustment to something close to the base or most abundant color in your intended piece so it won't stand out so much if you miss a few places) and then paint on top of it... kinda like a coloring book or paint-by-number :)
That was probably less than helpful, but maybe not.
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. ^^