The folks working on Armory have done a wonderful job thinking about many of the risks associated with Bitcoin and Paper Wallets. The have even gone as far to consider the risks of a compromised printer with a feature they call SecurePrint™.
In the Certificate Authority world when managing secrets that can not be kept within a Hardware Security Module (HSM) we go a further by using similar key management tools on Tempest hardware physically located in Faraday cage under rigorous ceremonies designed to ensure every single step performed is confidential, verified and audited.
For the individual moderate Bitcoin holdings Armory provides a robust story for managing wallet keys and producing paper wallets especially when paired with something like the PiWallet. That said since once doesn’t need to physically take your Bitcoin (they can just take a copy of it) make it their own how you store it is also important.
For valuable secrets that must be stored on paper a Certificate Authority would fold the corresponding paper in half taping each of the open ends close using tamper evident seals.
They would then place each sealed paper into their own opaque tamper evident bags keeping inventory of the bag and seal serial numbers, who was present and then storing the bags and inventory in separate secure locations.
This not only makes it possible to detect what has happened with the stored paper but protects it from water as well. Consideration is also given to what kind of paper and toner is used; for most scenarios one would use archival quality paper and high quality toner. But paper burns and toners are made of organics that can break down in heat so electronic copies are often also kept.
When it comes to those electronic records the choice of what media you use to store those values is important, as many types of media are not reliable for long-term storage. Today I would use the MDISC which effectively engraves the data into a disc that is still readable by modern DVD and BluRay players promising the disc to be readable for 1,000 years.
Even though most data being stored would already be cipher-text one never wants to rely on a single point of failure and for this reason another layer of crypto would typically be used. Commonly this is as simple as using GPG or TrueCrypt with a password to encrypt the data you are going to write to the disc in-turn managing the security of that password carefully.
At this point your down to being concerned with the physical protections your storage facilities offer and ensuring you have long term access to the hardware and software necessary to use the artifacts captured above.