Could use something like PaperBack[1], which can handle >1MB/A4 sheet. Combine that with a decent quality printer/paper and autofeed scanner, and you could quite easily dump a few hundred MB without too much manual effort.

I believe "offline wallets" require only the (relatively) short keypair to be stored, which would make this a practical solution.

If they're using much fewer wallets, or are confident that the paper would be last-ditch restore only, they could print (semi-)human-readable data in an OCR optimised font, to give them some chance of recovering from otherwise corrupted media. I'd put more trust in the automated bitmapping with sufficient redundancy & forward-error correction, but wouldn't discount extra semi-manual methods for any high-value wallets.

[1] http://ollydbg.de/Paperbak/

They would be done in the way that I personally do, or at least something similar. The private key is split using Shamir's Secret Sharing Scheme into several pieces, which is then printed as a high-redundancy QR code and then hidden. The key only needs to be 256bit, so there's not a lot of data to hide.