The map elements will come down primarily to two things: Purpose and Style

Purpose: What is the map being used for?

A map can be used for many different things: showing the duchies of a country, showing the countries of a realm, showing the continents of a world, showing the cities of a continent... etc. This will pretty much determine your labeling and what is required, which is based solely off what you want to show to the audience. If you want to show the countries AND the cities, then you mix up your labels usually with the larger sized font representing the larger sized area (so a Countries label would be in a bigger font than a Cities label). If you start adding more detail and want to show town as well as cities, then you need to have a way to demonstrate the difference, again this can be as simple as font size.

If your map is showing the territories of various factions then you may wish to highlight their borders with different colours or pattern overlays so the audience can quickly see who controls which territory (again, this would be the primary purpose). If you want the audience to know how they might get from one city to another then you'd throw on some roads. If the maps purpose is to highlight the key trade routes then this can highlight roads in different colours, etc. Similarly if sea faring is important then you might want to put some navigation lines (the lines that cross over in the sea or look like a star). Some typical elements that you might find are:

1) A Key/Legend - The little box that highlights the main features of your map. This can show that a small black dot next to a name indicates a town, whereas a large white dot is a city. A dotted line is a road, but an unbroken golden line is a primary trade route. The more detail your map has that isn't instantly obvious to your audience as to what it is, the more need you'll have for a Key. You may also have a secondary key depending on a specific purpose, such as the factions mentioned above (or Houses, or Countries) where people might show the heraldic shields in a separate key so the audience can view which areas belong to which groups.

2) Scale - Not always necessary but if you want the audience to have an idea of how far one city is away from another then you need a scale. The scale you use is primarily dependent on how big your map is. Drawing a world map then doing a scale "per mile" is kinda pointless as a mile probably won't be noticeable on such a large map. Sometimes cartographers will use the borders of their maps to represent the scale (which is why you see so many stripped borders) as it almost creates an invisible grid on your map). With something like a battle map (for D&D etc) then a scale grid is near enough always put on if it's not obvious what the intended scale is (typically 1sq = 5ft for player scale maps).

3) Compass - Some people like to know which way North is, again, this isn't vital, but depending on what you want the audience to know is something that can be added in, and can also be tied in with your ocean navigation lines.

4) Relief - If showing the height of your maps is important, from deep oceans to high mountain peaks then you can put down some typical relief lines as shown in national grid maps; lines around a mountain that get closer together and smaller as they reach the peak. Though they're not often seen for mountains you do get them quite a lot with oceans, where a line tracing the coast shows the transition from shallow water to deeper waters, etc.


Style: How to design those above elements?

This part is open to the artist really and is all personal preference. Some people don't have fancy borders, those with more artistic illustrative talents might paint dragons or sea creatures in the corners of their map, etc. but there's rarely any real purpose other than to make the map look pretty. Where someone uses a white circle to represent a city, the next person may draw a small cluster of buildings as an icon to represent it, again this is all personal preference. The detail of your heraldry, the colours and shades you use in your maps, it all comes down to finding your own style and how you like to try and tie everything together. There's no right or wrong way, some artists can add lots of detail to their map, but equally a more simple map can look as beautiful.



Hope that helps.