Followup question: if the general population of Europe in the middle ages was very religious, why wouldn't any old peasant who was looking for a better life just become a priest?

The biggest impediment to this would be literacy. In most of Europe literacy wasn't particularly common until the Industrial revolution; by that point books were both cheap thanks to increasing industrialization, and countries began enforcing and financing public educaiton for the masses (the first law that I'm familiar with like this was instituted in Sweden in 1686, and even then it took nearly a hundred years for literacy to reach close to 100%). I should point out here that many recent theories suggest that ancient Romans tended to be literate, and many of those living in both Classical and Hellenistic Greece probably were too.

A priest generally needed to be able to read (both liturgical texts and correspondence from his superiors and the like), and many monks were able to write. This simply wasn't a skill that the lower classes possessed. Many may never see a book other than the Bible, and farming or fishing didn't require the ability to read.

On top of this knowledge of Latin was requesite; at least the ability to recite it clearly and accurately were required. In England for instance there were laws on the books that covered the "Benefit of the Clergy": a person could claim that they should be tried under church law, which usually had much more lenient sentences, instead of secular law. All most people had to do until athe 13th or 14th century was pass a literacy test by reciting Biblical passage. This did lead to exploitation, but literacy was low enough that for at least a couple hundred years secular and religious courts didn't see it as enough of a problem to change the laws. Conversely, even a tonsured priest or monk would need to be able to do this to fall under clerical law, and so most were probably proficient at doing so.

Your best chance as a peasant to join the clergy was to join a monastery at a young age; you had a chance at an education and until then could work the vast estates owned by the church. But advancing into the priesthood was difficult. You usually needed approval by a bishop, and they were only likely to appoint you if you had sufficient education and (often) political connections. Younger sons were often trained to be clergy, and Bishops benefitted politically by granting parishes to the noble sons of local rulers. These men also had the advantage of recieving good educations, giving them a clear advantage over non-noble clergy.

To put it into an easy-to-explain context, look at a highly respected profession today, like a brain surgeon. It's possible to become one from nearly any background. But you have a much, much easier time doing so if you are able to afford the massive amounts of training and college required to do so. Now imagine if you were a poor rural American, and scholarships to universities didn't exist. Also imagine that you never went to school, or stopped going when you were ten or eleven. What do you think your chances of becoming a brain surgeon would be? This was similar to the circumstances that the peasantry would have found themselves in if they wanted to become ordained.

Ultimately, the core of the problem is that education was required to join the priesthood, and education was very, very expensive. Even if a family could somehow scrape together the means to educate a child, the local lord would have to give permission in most cases for them to do so. Now if you were a feudal lord, and your income depended upon the peasants working your land, would you want to spare a strong set of hands because they wanted to become a priest? Probably not.

This article, while short, describes in simple terms medieval educaiton: http://www.historylearningsite.co.uk/medieval_education.htm

Followup: how much would the answer to this vary by the different branches of christianity in Europe?