The size of your map means that you should focus on story-relevant points of interest rather than attempt to realistically depict every city and town. Unless civilization is very new to this continent, you can pretty much guarantee that every square kilometer of habitable land is occupied to one degree or another. While the number of actual cities will be few, given a medieval tech level, there will be tens of thousands of towns and countless villages dotting the landscape. That said, I'll try and give you some good points to consider.
The best way to imagine medieval population distributions is to imagine a tree. Villages are like the leaves, towns like the branches, cities like the limbs, and the capitol (or most significant habitation) like the trunk.
Villages contain anywhere from 200 to 500 inhabitants and will either be surrounded by farmland or be adjacent some resource gathering operation such as logging or mining. Villages will have a dirt path or dirt road connecting them to the nearest town. The length of this road was typically the distance a man with cart could travel in a third of a day. As stated earlier, there will be a countless number of these given the size of the region you specified, so I would not bother placing them unless they are story relevant.
Towns will have between 500 and 1000 inhabitants and also host the marketplace for a region. Each town will have many villages that feed into it and will often, but not always, be adjacent to something facilitating commerce such as a navigable river, coastline, or developed road (a rarity in the middle ages). In the event that none of those conditions exist, the town will instead be a waystation for travelers and traders, such as an oasis town in the desert or the midway point between a vast expanse of wilderness. Towns will also be the minimum size of habitation where you might find a local lord - most often a baron(ess), but sometimes someone of a higher rank. If this is the case, then that town will most likely be adjacent to some defensible position such as a hill, cliff top, river island, or the like. That defensible position will be where the local lord has his castle (the size and construction of which is a whole other topic).
The towns of a region, just like villages, will surround the cities they support. The cities will have populations we would today consider small with between 1000 and and 8000 people. They will almost certainly be on a coast, along a major navigable river, or next to a lake because waterborn craft were, by far, the most efficient means of transporting goods over distances. For the rare exceptions to that rule, the city will instead be placed where it is because it sits at the crossroads of a major trade route or controls access through a mountain pass. They will also very likely be the home of a higher ranking member of the nobility such as a count, viscount, or possibly even a duke. Just like with towns, if there is nobility in the city, their castle will be built at the most defensible position possible. The most important takeaway point though is there will be relatively long distances between cities, even if all of them are along the same coastline or river.
Finally, there are capitols. Again, relative to modern standards these will be small. Paris in the 14th century had somewhere around 200,000 people living in it and it was one of most populous cities in all of Europe. These will be the most widely spaced habitations of all. There will be many days travel between cities of this size and most often, a country will have just one(hence 'capitol'). It will almost certainly be the seat of power for a country's king.
Just like the preceding tiers of populations, capitols will be 'fed' by major roads or navigable rivers from the cities supporting it. These will almost always be not only located on a major river, but also one that opens up into sea. For London, it was its position on the River Thames which opened up into the Baltic Sea. For Paris, it was the River Seine which also opened up into the Baltic Sea. For Rome, it was the river Tiber which opened up into the Mediterranean which, itself, granted it central access to all the major cities that had been inhabited since antiquity.
The whole reason Capitols got as big as they did was because they sat along the most logistically ideal location for importing the tremendous amount of foodstuffs they needed. The rivers would bring in goods from the interior while the coasts would bring in goods from all the coastal cities. The rivers would also supply the city with drinking water for the inhabitants as their proximity to salt water meant wells would be easily contaminated with brackish water. So, if you place a very large city somewhere, regardless of whether it's a capitol, you should do so where it will have ideal conditions for trade, access to fresh water, and some means of getting large amounts of food.
In conclusion, when placing towns and cities, try and imagine them as a tree with the leaves being villages, towns branches, cities limbs, and capitols the trunk; each tier supporting the one above that. Remember that the larger and more important your city is, the more selective you have to be as to where you place it. Adjacency to seaborne trade lanes, access through difficult terrain, a supply of fresh water, and defensible terrain are all factors you need to consider.
