You could even place some dummy data before the main store, with redundant storage in another format - if you read ("decode") the data and it matches (like you suggest) something carved in a block of stone surrounding it, you know you have the process down, and you can go on and decode the main store.
But that's not the whole of it. Once they can read the 0's and 1's, you need to tell them how to interpret them. So you need to provide (at least) an ASCII table in some extremely durable material.
The rest of the information (on how to interpret the data) can then be stored in the first mega/gigabytes of the binary data. Plain text ASCII only, ofcourse. No pictures, audio, or video. You could only include such data once you've told them how to build a computer and all necessary software.
I think you're better off storing a computer and a self-sufficient powersource in a vacuum, virtually indestructible structure. Has the added benefit that you can make cool movies about it :)
That's OK. At these data density scales, a small room full of 10"x10" tablets would provide space for a LOT.
I'd imagine you'd encode media in some simple lossless RLE format which you would then describe.
Imagine being an architect in the year 27,000 coming across this stuff. I'm sure the value would be immeasurable, especially the video and audio! Can you imagine having HD "documentaries" from Ancient Egypt or Greece? How cool would that be!
As you can see, this stuff fascinates me.
So, storing the information is one thing - being able to read it is a completely different beast. If you would really want to store something for a few thousand years, you're probably better off chiseling it in stone. Then you only have to make sure people (or aliens?) can read our letters and understand our words.