Hi there Nerevar, welcome to the Guild.

After a bit of trial and error, this is what I use to do my mapping:
--regular eraser
--mechanical pencil for sketching and sometimes adding shade
--0.1 Copic Multiliner SP pen for final product
--I also find Photoshop to be a very useful tool for colouring and annotating maps, but prefer paper and pen for the actual drawing and design

This might sound a bit heretical to some people on CG, but I actually think that just about any ball-point pen can work for making a map. Those ones with the four colours are OK. It depends a lot on the level of finish you are going for, how you plan on using the map, and other aspects of your technique (for example, if colouring a map digitally, it is probably best to invest in a quality pen).

If you are interested in developing your artistic abilities, there are plenty of options out there: I don't know about different brands, but watercolours are perhaps your best bet for coloured pencils; just take care you get the appropriate paper, or else your image will start to warp.

Have you got any maps or practice images you're able to share?

THW