Hello everyone :)
This is not a detailed guide but a more conceptual one. It explains the thoughts and steps i use in making a map. This guide follows the process of creating "the Fall of Jerusalem". I'm using illustrator for vectoring so i wont provide any shortcuts and detailed explanations, but all vector programs have more or less the same tools so all u have to do is use the help menu and some videos and you should be fine.
First Step
Here I would like to stress the importance of good research and planning. There are extensive amount of maps on the web about any subject you require, so take your time and explore. If you have some printed maps it would also be very usefull.
For this map i started my search on maps of the crusades and after some disappointing hits i finally came across the very good maps of Ian Mladjov from the University of Michigan. I also found some other good maps with important crusader forts in each of the kingdoms. The main thing to look for are maps with towns and provinces (if your lucky) as they are very useful for naming and planning your territory composition.
Here are some examples of the maps used:
http://sitemaker.umich.edu/mladjov/files/outremerreference1143.jpg
http://medievalcoins.ancients.info/maps/Crusader_Levant_map.JPG
One more thing to start considering is the look of your map, try to see how the maps of the period looked, what names we're they using and so on. There's a lot free vector elements you could use to add some character to your map and make it more visually appealing :) Think about coat of arms or flags for your megabonuses, read some history about the map or period your trying to recreate. How they depicted the ships, fortresses or airports. Trust me you can find some interesting information and also educate yourself a bit (which is always a good thing :) I wouldn't like to provide links for the vectors here, but u can always search for "free vector download". Just be VERY careful what and from where you download, and keep in mind we're limited to 2MB per map.
After arming your self with all the resources u need it's time to go to the next step :)