http://forum.bitcoin.org/index.php?topic=24642.new#new
What I envisage is a program that can print the key pairs off the grid if required and print either directly to a printer of via a pdf file. Ideally, you would be able to use a template for print the paper money on to standard sized sheets, such as perforated business card printer sheets. You could make it such that you fold the card to hide the private key and seal it with a tamper-evident sticker, but leave the public key and QR code linked to the block explorer address visible, as well as having the denomination value printed on the card. Basically, it is a home made Bitbill, but without the extra security features.
Then, either the program or the user loads the card by sending bitcoins from the user's wallet to the paper money address.
Since I've made and loaded the money myself, I don't need to trust a third party keeping a copy of the private key. I do however, need to keep the paper money physically secure, just like the other money in my wallet.
Now when I go to a restaurant and need to pay my bill, I just hand over the required amounts of paper Bitcoin money to the owner, who then reveals then private key and transfers the balance to his account. I could also keep a card in my physical wallet with an address of my own for receiving change if I don't have the exact change in paper money.
Would anyone be interested in implementing such a solution?
Please understand what this is and isn't supposed to be. This is a means to make Bitcoin as portable as paper money without needing to carry a laptop or smartphone to make a payment (okay, the merchant still need technology, so it is perhaps more akin to a prepaid debit card). This is not meant for storing large amounts of Bitcoin, only for what you would ordinarily carry in your physical wallet. This is not meant for people receiving the Bitcoin paper money to be able to spend again. It is for single use only, as the recipient has no way to know that you have not kept a copy of the private key and can spend it before they redeem it. This is intended to be lower cost than BitBills, and available in any desired value.
Addendum: The major problem with implementing such a system right now is the inability of the standard client to import key pairs. So a useful interim solution would be a website running siba's patch that allows you to input a private pair and make a transaction to another Bitcoin address. This could then be used by the merchant to redeem the paper Bitcoin money.