Your question encompasses a library's worth of material so in due course I'm going to include a bibliography at the end of this answer (which is to give a brief introduction) which should help you not only to navigate, for the purposes of this answer, the maps of medieval Europe, but also the theological and philosophical thought behind medieval maps behind them.

The orientation, contents, and overall function/purpose of a map was quite diverse even within the various map-making traditions that existed – this answer will focus mainly on European medieval maps – the mappae-mundi (Latin: “cloth of the world”) tradition that flourished in Europe from approximately 1000-1450 CE.

Before answering the what/where/hows of the mappae-mundi tradition, it is important to consider for a second what their purpose was. They most certainly were not made with practical navigation in mind – they are usually found in small manuscripts (see the Psalter World Map) or are massive in size, mounted onto walls (see the Ebstorf Map). The word “map” did not exist as a dedicated word in the medieval period - mappa meant “cloth”. The best word to describe it might be carta (“diagram”), but they were much more than that. The late 13th c. Hereford Map in England describes itself as an estorie (Norman – “history”) – these maps intended to act as a seemingly chaotic graphical and textual summation of history, geographic, natural, and ethnographic knowledge, biblical and classical stories, but all (usually) tidily ordered within a divine pictorial framework.

You’ve asked a really good question – what was the protocol for deciding what went at the bottom or top of a map? Mappae-mundi tended to follow a pretty standard protocol from approximately 1100-1300 – before and after that, there is a bit of variance, not drastically dissimilar from the above period. They tended to adopt a large amount of classical/late antique knowledge – Macrobius popularised the notion that the world was divided into several climate zones going North to South – a frozen zone, a temperate zone (which is what the mappae-mundi are showing) and an impassable torrid/burning zone; another temperate zone and another frozen zone is then on the other side of the burning zone. Mappae-mundi were really mapping the known world – the northern temperate zone of the earth (Note: unfortunately I can’t give a comprehensive answer on how they decided/”knew” which way was North itself, but the short answer has in part to do with the recording of celestial objects – I’m going to try and find answers for this and link them below.

This known world is usually referred to as the orbis terrarum, or circle of lands, and Isidore of Seville popularised the idea of representing it in a simple “T-O” diagram. The known world was represented as, broadly speaking, a circle (Important note: the mappae-mundi tradition is not evidence that medieval people believed the earth was flat – it was widely known that the world was a spherical object) which would be divided into three parts – if you can imagine the letter T being inside a circle (hence “T-O” map). Asia was on top, Europe on the left, and Africa was on the right – the Garden of Eden, the earthly Paradise, was believed to lay somewhere in the East, beyond India, and was often firmly represented on the top of these maps – and thus, medieval European maps were orientated to the East.

As for what they were putting in the map itself, where, and why – this is a question you could spend your life dealing with! A locations of peoples, monsters, and creatures could have to do with a myriad of historical, mythological, and biblical reasons – the division of the world into three parts itself having to do with Noah’s three sons – Shem, Japheth and Ham – spreading out into the world. The maps present multiple time periods simultaneously; often times they show images of creation, images of Noah’s Ark on top of the Mountains of Armenia (which is after the end of the Flood), the conquests of Alexander, the Crucifixion, the Apocalypse, all at the same time.

Thus, the overall emphasis of these maps aren’t really on any geographical accuracies – geography becomes an malleable space to serve as an aid to help drive the maps didactic and imaginative function. European mappae-mundi tend to be (but not exclusively) be orientated eastwards, towards the Garden of Eden (which was believed to be far to the east beyond India and Sri Lanka), with Jerusalem occupying usually being put in the centre of these maps. Traditions exist all over the globe during this time for the orirentation of maps, though I do not know enough about them to answer about them – Karen C. Pinto has a great book on the Islamic tradition of Cartography which will probably answer the question as to why they orientate their maps generally to the South

Brotton, Jerry, 2013. A History of the World in Twelve Maps. London: Penguin Books Ltd.

Delano-Smith, Catherine, & Roger J.P. Kain, 1999. Studies in Map History, Vol. II. English Maps: A History. London: The British Library.

Edson, Evelyn, 1997. Mapping Time and Space: How Medieval Mapmakers Viewed Their World. London: The British Library.

Hiatt, Alfred, 2008. “The Map of Macrobius before 1100” in Imago Mundi, vol. 59, no. 2, May 2008, pp. 149-176.

Kenny, Anthony, 2007. A New History of Western Philosophy: Volume II – Medieval Philosophy. Oxford: Clarendon Press.

Kieckhefer, Richard, 2014. Magic in the Middle Ages. 2nd edition. Cambridge: Cambridge University Press.

Kline, Naomi Reed, 2001. Maps in Medieval Thought: The Hereford Paradigm. Woodbridge: Boydell Press.

Mittman, Asa Simon, 2006. Maps and Monsters in Medieval England. Abingdon: Routledge.

Mittman, Asa Simon, 2012. The Ashgate Research Companion to Monsters and the Monstrous. Surrey: Ashgate Publishing Limited.

Muldoon, James, The Expansion of Latin Europe, 1000-1500: Travellers, Intellectuals, and the World Beyond Medieval Europe, edited by James Muldoon. Surrey: Ashgate Publishing Limited.

O’ Reilly, Jennifer, 2019. “Islands and idols at the ends of the earth: exegesis and conversion in Bede’s Historia Ecclesiastica” in History, Hagiography, and Biblical Exegesis: Essays on Bede, Adomnán and Thomas Becket. Abingdon: Routledge, pp. 36-64.

O’ Reilly, Jennifer, 2019. “The Multitude of Isles and the Cornerstone: Topography, exegesis, and the identity of the Angli in Bede’s Historia Ecclesiastica” in History, Hagiography, and Biblical Exegesis: Essays on Bede, Adomnán and Thomas Becket. Abingdon: Routledge, pp. 88-112. Pinto, Karen C. 2016. Medieval Islamic Maps: An Exploration. Chicago: University of Chicago Press.

Scully, Diarmuid, 2016. “Medieval Maps and Diagrams” in the Routledge Companion to Medieval Iconography. Edited by Colum Hourihane. Abingdon: Routledge. Pp. 399-411.

Strickland, Debra Higgs, 2003. Saracens, Demons, and Jews: Making Monsters in Medieval Art. Princeton: Princeton University Press.

Woodward, David, 1987. “Medieval Mappaemundi” in The History of Cartography: Volume 1 – Cartography in Prehistoric, Ancient, and Medieval Europe and the Mediterranean. Edited by J.B. Harley and David Woodward. Chicago: The University of Chicago Press, pp. 286-370.

While you're waiting for a more specific answer, you might be interested in these map threads:

Was North always on the top of maps? by /u/terminus-trantor

When did it become standard for "north" to be on the top of a map? And why? by /u/Valkine