So far everything has just been flat layers of colour, often blended in some way. I'm sure that most people would be able to adapt the ideas I've presented in their own graphic programs (as long as they are capable of handling layers). Adding specific depth might be a bit trickier.
In Photoshop I use the "Bevel" layer style in combination with some of the techniques already discussed.
(Oh, before I go much further, I forgot to mention that the wood texture of the boats and piers had a rough monochromatic scratchy texture applied to it. A bit of texture always stops things looking too flat.)
To focus on the technique for the tunnels, I'll strip away all of the other colours that have been applied so far.
First, I apply a new stone texture to the corridors.In this case, it really doesn't matter what the texture is, as long as it's a bit jagged and rocky looking. A new layer is added (on top of all the other textured layers, but beneath the drawn layer), then each room is selected with the magic wand tool...(when you hold the shift key down with the magic wand tool, you can select multiple areas). Like before, I use the "Select-> Modify -> Expand" tool to increase the selected area by a pixel or two.
Once the relevant area is selected, a paint bucket fill can be used to give all of these areas a distinct colour...I just use black because it's easier. The layer style has a "spiky bush" pattern overlay applied to it.
Next we add an "inner shadow", it basically gives the appearance that a hole has been cut out of some paper and you can see the material underneath. In this case the "material underneath" is the pattern texture we just applied to the rooms and corridors. For this map I've made the drop shadow 15 pixels deep and have softened it by 10 pixels. For your own maps, you might want to play with the sliders on these values until you get something that you like. The bigger the bevel size, the deeper the walls will look; the lower the softening, the harder the lighting will look for the map. I went for something that conveyed the wall depth without overwhelming the image, and softened it to the point that the walls look a bit more worn and "cave-ish".
Now for the bevel. This is a simple technique in Photoshop, it's just another layer style to add to the others already in place. I simply add an "inner bevel" because we want the effect to be applied inside the selected room and corridor areas. I make it "chisel hard" so that the contours of this bevel will specifically follow the contours of the walls, it is marked as a depth of 100% and has a direction of "down". These last aspects don't really make much difference except to change the strength of the highlights and shadows about to be created.
For the size of my map, I make the bevel 10 pixels wide and soften it by five pixels. This accents the walls where the shadow lies, and provides a subtle highlight to the un-shadowed walls (giving the illusion that a light is reflecting off these walls and back into the chamber/passage).
It's a pretty simple effect that doesn't require too much thought about where to put shadows and where to put highlights...everything is basically automated.
If I was to do the map again, I might modify this technique to get shadows on the beaches...but the important thing for this map is the hidden passages and cool stuff embedded within the secret cove, so that's where the detail stays. Extra detail is nice, but we don't really want too much detracting from these dungeon tunnels.