The last topic to cover before getting into the specifics of the Majestic Wilderlands is religion. When I work on settings I define religion as the culture that surrounds the worship of a deity or deities. This keeps my focus on things that are useful for roleplaying NPCs and creating locations rather than just coming up with magic items, artifacts, and monsters. And above helps me avoid treating the deity as nothing more than a powerful monster.
In our history feudal Europe was dominated by the Abrahamic regions, (Christianity, Judaism and Islam). For a short while in the very early middle ages just before the rise of Islam you had Zoroastrianism centered in modern Iran. Christianity had two main divisions the western or Catholic, and the eastern or Orthodox. Islam had it own division between the Sunni and Shiites. Understand I am simplifying a complex subject. What I am going to focus on is the role of religious culture within a feudal society.
Religion played a dominant role in the various feudal societies. And that role was handled in three main ways.
Theocracy - this is where the religious hierarchy is also the ruling hierarchy of society. In our history the Sunni Caliphate of Islam came the closest to a theocratic state during the Middle Ages. In practice, theocracies split secular and religious authority at each level of authority. For example the bishop ruling a region would have separate individual handing religious, military , administrative, and judicial duties. With people involved in the military, administration and judiciary are ordinary lay adherents of the religion. However the person in charge, in the case the bishop, would be a full priest/minister of the dominant religion. Also the judiciary may be split between ordinary courts to hear criminal and commercial cases, and a separate court run by the clergy to hear crimes against the moral order. The specifics of which differs based on the religion involved.
Caesaropapism - society has a separate secular and religious hierarchy however the head of state is also the head of the dominant religion. The Byzantine Empire and the Orthodox church is a good example of this. Later during the Reformation some of the protestant denominations fall under this category particularly the Kings of England after Henry VIII and the Church of England. The type of relationship between religion and society as a whole is characterized by a strong central government. A skilled ruler would use both his religious authority and his secular authority to keep both heirarchies in check.
Church and State - this is the situation of western Europe during most of the Middle Age. You have the state, the various kingdoms and other sovereign realms. Each with their own hierarchy, customs, and laws. Then you have the dominant religion in the form of the Church with its own hierarchy and its own leaders. In this setup, the church has a lot of moral influence but not a lot of actual power. However in many cases the nobles would have agreed to allow clergy to only subject to religious law. And for much of the Middle Ages the religious courts were much more fair than the secular courts. Also note that "clergy" in this case is far more expansive than what we are used to today. It covers just about anybody who is actively employed by the dominant church. They don't have to be anointed or ordained priests.
Specific to the DnD/fantasy style campaigns most of us run is the fact we use polytheistic pantheons. A legacy of Howard's Conan, Greek Myths, and other sources used by Gygax, Arneson, and other early RPG authors, campaign settings with Monotheistic religions are the exception not the rule. Obviously this is going to make the resulting feudal societies a little different than what happened historically. The good news is that there are ways to having both.
The first things to remember is the idea of henotheism. Henotheism is where people are adherents of a specific deity or religion don't deny the existence of other deities and religions. In a way this makes sense for a DnDish setting where clerics have similar lists of divine spells. Something is fueling the other guy's healing spells right?
The default situation would be the religion of a specific culture. The default religion would a pantheon and each deity covering some area important to that culture. A culture living on the coast would have a different set of deities than a culture living on the steppes.
If they are friendly to another culture than their two respective religions would be friendly. If not then the two religions are rivals. A wrinkle on this is when a less sophisticated culture comes into contact with a more sophisticated culture. Because the more sophisticated culture usually has answers for things that the original culture haven't thought of. And because they are now in contact as part of a wider world, the original culture need those answers as well. This can setup conflicts in the original culture that result in factions. Which of course can lead to various types of adventures.
One way to have a monotheistic style religion in your campaign and still retain a multitude of deities is use the idea of a deity's chosen people. In my Majestic Wilderlands the Ghinorians believe themselves to be the chosen people of the Mitra, the goddess of honor and justice. While they don't consider all other religion to be enemies, their belief as a chosen people leads to the Church of Mitra occupying a similar role to our own history' Catholic Church in the lands they dominate.
The last comment I will make is that you need to consider the influence of the elves and the other long lived races on religion. My own take is that the elves have a huge influence on the culture and religion of their friendly neighbors. Their longevity allows them the time to manipulate the shorter lived races to achieve security for their realms. And often that involves them filing away any objectionable aspect of their neighbor's religion. Or even just outright replace their neighbor's original religion with a variant of their own beliefs.
And if your elves are heavily influenced by Tolkein's works, like mine are, then the elves have a divine connection as well. In the fact they actually are witnesses to the words and actions of divine beings. In Tolkein's case that was the Valar and Maier as well as the "heaven" of the Blessed Realm of Valinor. In the Majestic Wilderlands I implement this as the Sylvan culture. Around each elven realm there is a zone where human cultures are heavily influenced by the elves and other demi-human races. Because of the elves, these cultures share certain deities and moral values even when they are thousands of miles apart.
To date we covered the general ideas of feudal society in regards to the nobles, peasants, towns, and religion. Next I will dive into how I implemented this for the City-State of the Invincible Overlord in the Majestic Wilderlands.