It would be a collection of lithographically etched plates. These are stable across a wide collection of conditions. The coding scheme would be reed solomon or a variant of it, or possible even just massive duplication with checksums. Multiple duplicate backups of the entire data would be stored in geographically disparate locations. This reduces the "asteroid hits <city>" problem. A wide range of different technologies would be used, randomly, across the copies. This reduces the likelihood of systematic catastrophic failure due to a specific technology not working as expected.

This is not that different from how current millenia-scale data storage has worked for... well, millenia. The primary challenge is in finding a universal key (if somebody comes along a million years later, will they share enough context to decode the archive?)