Probably stone tablets. Once written, no moving parts, and they last thousands of years. And you can find them laying around anywhere for free.
Edit: quick math. If we assume roughly one bit per square mm, you'd need about 24,000 km^2 of stone. So if you happen to be located in Northern Canada, you're all set.