If you are going to encode it in a non human readable format, there is little point to storing it on hardcopy over electronic storage medium (hard disk, USB flash, floppy, etc). You will still need a computer to access it.
There are some fonts out there specifically designed for OCR, but in practice any little spec of dust or dirt can change how the computer reads it (an "O" can become a "Q" for example. And "1" is easily misread as "i" - in some fonts they are even 100% identical). So OCR is OK for text that you can spellcheck, but not for other kinds of data.
Depending on the kind of data, you could include something like a printed checksum to verify you read it write.
To conserve space, just make the fonts as small as you feel comfortable reading, use both sides of the paper, possibly reformat the data to utilize more space on the page, and use thin lightweight paper. And include an additional electronic backup so you don't have to bother OCRing until the world ends next Thursday.