A lot of work. "Modern" maps tend to be a lot more precise than the "antique" types. So I would start off with precisely defining the geography of my land. Make up the profile, the heightlines of the land (and ocean, if you want to show these). Then you can decide on a style.
Nathan did a small tutorial about the way he shaded his great Gallia maps. With a little effort, you can use that as a basis for a crosshatching shader, or simply use it as a grey overlay.

If you are going for a physical map, you don't even need any kind of relief shading. Simple colouring of different heights can look quite good... I have an old 1960-ish Reader's Digest World Atlas which uses such a technique.

A graticule, showing the exact positions of the geography, is also something that should be added.