I recently came across one of the letters online and became curious to learn how it survived all these years.
My understanding is that wet climates tend to be bad for the survival of paper notes. I found it surprising that they survived Britain, but I get that it was likely stored someplace dry.
Beyond that, I guess I'm curious whether it's common to save the personal correspondences of kings, generally. Do we know the story of how we came to have these letters today? Were they kept safe by someone with historical foresight? There's got to be a story here, no?
I can't speak to Henry VIII's letters specifically (/u/yermawsgotbawz has covered this) but the question of which materials remain extant from this period is often very much a matter of chance.
Each item's chances will be different depending on the type and quality of manuscript/book. High quality paper stored indoors is likely to last well - lower quality paper in damp storage conditions not so much (the King's letters obviously start with a good chance of survival because of their inherent value).
From there, the popularity of the document may impact survival. Margaret Spufford's Small Books and Pleasant Histories talks about how a lot of cheap printed material from this period probably ultimately ended up in the privy. Books which were known to be very popular sometimes don't survive well simply because they were 'read to pieces' and fell apart long before our era (The Court of Venus is a likely candidate for this) but there is a threshold at which so many copies are printed that the likelihood of survival stays quite good. (This theory is definitely a hot topic for debate in both history and literature studies).
When it comes to manuscripts, the value and usefulness of the documents have a big impact. Documents like indentures and land records are very useful and likely to be deliberately maintained. Family letters will be collected together by relatives and intentionally kept. House books, commonplace books and rental records often survive partly out of ongoing usefulness, partly because paper was pricey, and once one user was done with the book, another owner would keep using it to make use of the remaining paper. Philip Henslowe's diary - one of the most comprehensive records of the business side of an early modern theatre - is like this. A relative (his brother in law, I believe) owned the book first, and then Henslowe continued to use it for his own record keeping. By this time, it might already be an old document, and of enough interest to seem worth saving.
Sometimes items survive simply because they have been stored out of sight somewhere!
Conversely, any number of unfortunate accidents can happen to destroy a manuscript or book. Fire was a common hazard, and to a lesser extent, so is water damage. There's also the risk of the materials just degrading over time. Gabriel Harvey heavily annotated his copy of Livy's Romanae historiae principis, and 20 odd years ago when Lisa Jardine and Anthony Grafton wrote '"Studied For Action": How Gabriel Harvey Read his Livy', the annotations were pristine. Now, after much more scholarly attention and exposure to air, the ink has begun to blur and it has thinned the paper so that the annotations have a lot of blur and bleedthrough (you can see his books here, and I definitely recommend having a rummage through that site).
Attrition of early modern materials is usually a fairly complicated process with lots of determining factors much more significant than a wet climate. More often than not though, you're relying on luck for what makes it and what doesn't. Some books have better luck than others!