By priests and also by sisters and nuns, and by the lord and lady of the manor, by their parents and by their employers too.
Little Jehan and Louise, or young Murdoch and Ellen, or Tom and Betsy, or Diego and Isabel, would be taught by the parents to pray the paternoster and ave from earliest childhood. They would hear from strolling minstrels and jongleurs Mystery Plays, hear church settings sung, and as they grew learn also by heart from older children, their employer, their parents etc the more complicated credo.
Older boys with a good ear would assist at Mass and they’d often pass on their knowledge.
Again, parents were good teachers. They had learned the basics of the faith from their parents, reinforced by priests and religious and usually by the rest of the villages. Up through the 1400s from the 9th century when Charlemagne was crowned Holy Roman Emperor, England and most of mainland Europe were Christian, or were being actively evangelized. from the conquest in `1066 with the Norman ‘fusion’ even the Scandinavians were Christianized. So pretty much by the 12th century when universities were beginning to flower, you had a population which had been catechized for a few generations, passing on the basics of the faith.
Those kids I mentioned? They could go from country to country and start saying Pater Noster qui es in caelis and whether the listener was French, German, Italian, English—they would know what was being said. They would go into a church in whatever country and they would know what was being offered, whose sacrifice they were attending, and what the Body and Blood, Soul and Divinity, was being offered.