It's a very appealing style you have chosen. I hope you will be successful with it.
0. The borders between countries.
This should be one of the simpler things from the technical side, but might get heavy on the work you need to put into it.
Every graphics program should have a function that draws a dotted / patterned line. So all you need to do is adjust this function to the settings that look good, and draw the borders with it.
Now to define these lines: that's more problematic. Within common painting programs - pixel oriented or vector - I can see no other way than to define every single one of these lines by hand.
It should be possibl to simplify that by using a 3-D program to define the basic shapes of the countries, but I haven't tried it out yet.
1. Mountains: again I can only offer partial advise. I have no idea how Zalring did his, but here's what I would try.
Paint the basic hight-map of the mountains as a grayscale map. Either use real world data, or make something up using noise patterns and masks. As far as I know, there are several tutorials on this forum that use such a method to create "relief" style mountains.
Then, look for a "lighting" function in your painting program of choice. In GIMP, for example, this is under Filters/Light and Shadow/Lighting Effects. Don't forget to use your hightmap as a bump-map and experiment to get a good looking and high contrasts lightling.
Raise the contrast to a point where you have almost exclusively black and white, and then use this outcome as a multiply layer with a low opacity.
2. The best way I have found to create a consistent diagonal hatching pattern in a painting program is to draw an orthogonal stripe pattern, distort it slightly (using a noise or a spread function) and then rotate it to the desired angle.
It is quite difficult to get a seamless pattern in this way though, so if you use this method, you can either create a pattern that covers your whole map (even bigger than the final map - you need to account for the rotation), or make patterns at country-size and accept that they won't seamlessly fit at the borders.
There are several ways to colourize such patterns - create them in colour from the start, or do it in black and white and use this pattern as a mask for a coloured layer.
3. The map frame in the examples you gave is just a bunch of linework. Using selections or paths and stroking them is the easiest way to do it.
But I guess your question is aimed more at the lines of the graticule - the longitude and latitude lines with their slants and curves.
There's two basic methods that I would use. First is rather easy to use when doing "real world" maps. Just search the web for a map of your desired area and trace these lines to your map. Straight lines are the easiest to do, for the curves you need to play around with paths, splines or nurbs-curves a little. But you don't have to be too precise... if they fit the original map to a degree, the accuracy is usually enough.
The second method is a lot more complicated, but also more flexible as well as more accurate: do the math.
These lines - their position, form and direction - are based on the projection type you use for your map, and the position and alignment of your map. Each projection can be described by a mathmatical formula. Look it up, calculate your coordinates and draw accordingly.
There are programs out there that can do this for you, but I don't know of any that fit my requirements. NASA's G.Projector can do it, but it is mainly meant for global maps, and I found its scaling for regional maps lacking. But perhaps that's just me, and someone else can give more advice on that.