Sources on literacy in Medieval Europe seem to be all over the place, reaching from the popular "Almost nobody could even sign their name" to "There was at least one person in most households who could read and write". Here's a discussion on Stackexchange that lists some sources.
The sad truth is, we may never know how literate people actually were. We can be relatively sure that especially poor people didn't have any formal education and couldn't afford expensive handwritten books. But that doesn't necessarily mean people couldn't read and write at all. A basic level of literacy was useful for a lot of people, especially craftsmen and traders. Not so much that they'd read and write whole books but enough for basic bookkeeping or passing notes to someone who lives in a neighboring village. The thing is, those are not the kind of things that would be preserved until today. Paper and parchment were too expensive for such trivialities but we have evidence from Russia that people wrote everyday correspondence on birch bark. With no need to store these writings, most people would have probably just reused whatever they were written on to light fires or just thrown them outside where they would decompose within a few weeks.
(this kind of ties into a fun fact about why so few authentic chainmail shirts have survived until today. Not because they got destroyed by rust but because after they lost their usefulness in early modern times, they were cut up and reused to scrub pots)
Cave walls all the way. Can't risk someone accidentally break or throw away what you've written.