This is something that historians have debated a lot, and it's hard to answer definitively, partly because no one is exactly sure what a mindset really is. A lot of the current versions of the debate start with a book called "The Problem of Unbelief in the 16th Century," by Lucien Febvre in the '80s. Febvre argued that no medieval person could possibly have been an atheist-- not that they weren't atheists, but that they couldn't have been atheists, because the concept of atheism is unintelligible when your entire life is mediated through religion. Febvre turned out to be wrong on several individual points, but his broader argument, that some of our ways of understanding the world would have been totally unthinkable to a medieval person is probably true.

One small way to think about it: for most of the middle ages in most of Europe, very few people could read, and even those who could read often couldn't write. If you can't read, you can't understand religion other than by hearing people tell you about it or by coming up with something new on your own. Coming up with something new is both hard and dangerous, so most people's understanding of religion came from hearing sermons, or seeing religious plays.

There was a fair amount of criticism of both the church and the government. At the annual carnival, people sometimes dressed up as and mocked the local priests and nobility. But, for the most part, there wasn't a lot of criticism of the idea of the government or of the church. So people might say "Too many priests are corrupt and don't do their jobs" but they were unlikely to say "We don't need priests or churches."