Human beings can and will write on pretty much any surface that doesn’t run away fast enough.
But when it comes to the form those surfaces take, the field does narrow a bit. An ostracon, for example, is a broken sherd of pottery or sometimes stone with writing scratched into it, which you could call an early form of recycling. But as an organized method of record-keeping, it leaves something to be desired.
In considering how texts get shaped, I’d start with a distinction between public and personal writing. Public writing is meant to be seen by lots of people, and as such, it has to satisfy different requirements. You generally want it to be durable, visible, impressive. Stelae and similar structures are common in many parts of the world because they make for good monuments on which to carve whatever message you’re conveying: a decree, a triumphal boast, a boundary mark, or anything else you consider important. Walls are good, too — think of how many public buildings you’ve been in whose walls contain lists of patrons, information about the building’s history, or inspirational quotes. This is often written quite large, and high enough that it can be seen even when people are in the way, because the point is to make the message visible.
Personal writing doesn’t have the same requirements, and can be very ephemeral — unfathomable numbers of letters and scribbled notes have been lost throughout the millennia. Sometimes it’s even erasable, whether that’s through a wax tablet or unfired clay tablet, whose surface can be smoothed out again, or a palimpsest, a piece of parchment that has been scraped clean for re-use. (Recycling in action again: parchment was expensive.)
One of the earliest ways to compile writing was in a scroll: a long piece of writing material (papyrus, parchment, paper, fabric) rolled up, maybe with sticks at each end to facilitate the process and keep the scroll from getting crushed flat. These are found in many parts of the Old World, from Spain to Japan, and still see a limited amount of use today, whether as decoration on a wall or in religious contexts, as with a Torah scroll.
Why did scrolls fall out of use? They are inconvenient in some respects. If the text you’re looking for is at the end of the scroll, you have to wind your way through the whole thing to get it . . . and then if you want to compare against something earlier, you have to roll all the way back to the previous bit. Alternatively, you need a huge table on which you can unroll the whole thing at once. There’s no easy way to mark the location of the desired text for later reference, either — no equivalent to saying “it’s on page 137.” (Though is there such a thing as a scroll bookmark? A paperclip-type object you can put on the edge, which will stay there when you roll it up again? I can’t find any evidence, but that doesn’t mean it never existed.) On the other hand, scrolls offer certain advantages. The continuous surface allows them much more flexibility in juxtaposing text with images, and they have the ability — almost like a movie, or a comic book — to suggest the passage of time as you read along.
These days, though, we’re accustomed to receiving text in the form of a codex — the technical term for a book. Codices evolved out of hinged Roman wax tablets, and offer a number of benefits: not only is it possible to bookmark and reference specific points in the text, or to quickly flip back and forth between different sections, but you can edit them by taking off the binding and adding or removing pages. Furthermore, the covers help protect the more fragile interior against damage, and their shape makes them easy to shelve in an organized fashion.
Some codices, like the few surviving ones we have from pre-colonial Mesoamerica, are folded like an accordion, but this has given way to the style you’re familiar with, where pages are marked on both sides and bound only at one edge. (This, by the way, is different from how Mesopotamian clay tablets are read! There you “turn the page” by flipping the object along its horizontal axis, so that the reverse side is written upside-down compared to the obverse.)
Codices aren’t always written as coherent texts, though. In the days before the printing press, it wasn’t uncommon to collect separate pages of various things and bind them together in a codex — which is how we get partial survivals of some lost manuscripts, if a few pages were bound with something else, or high-tech scanning reveals the traces of earlier writing on a palimpsest.
The printing press introduces an oddity of its own. Rather than printing each page separately, early publishers often printed large sheets with multiple pages and then folded them up to create “signatures,” i.e. chunks of book that could then be bound. But of course those folds prevent you from turning the pages, so the purchasers of books used knives to slit open the folds and make the book readable. This means that your protagonist could realize someone’s library is just for show — because none of the signatures have been cut open yet!
Nowadays, of course, we have ebooks and ereaders and a hundred electronic ways of storing information. For some purposes (e.g. organization, searching, ease of copying) this is amazing! . . . but for durability, I’m afraid it kind of sucks. How many of you still have an optical drive on your computer, for reading CDs and the like? How about a drive for 3.5″ disks? Or 5.25″ floppies? And that’s just in the last 25 years or so. The format of the physical media becomes obsolete; the software for reading certain file formats goes away. The media itself degrades quite rapidly, and files become corrupted. It’s a massive problem for long-term data storage, and one I know the world of library science is working on solving.
But until that happens, books and scrolls and even clay tablets remain far more stable options for recording information than anything invented in the last hundred years. Properly cared for, they can last for centuries or even millennia.