Double-signature paper wallets? I believe it's possible to send money to an address that requires two signatures to spend.  But I am trying to figure out how this can be done with paper wallets. 

My understanding of multi-signature transactions: I can generate two keypairs, using two different machines and saving them in two different places.  Then funds could be transferred to the combined address, where they could only be unlocked by the presence of both private keys.

My question is, can this be done with ordinary paper wallets, such as from bitaddress.org?  Can I print a paper wallet, and have a friend also print a paper wallet, and then send money to the combined address so that both papers are required to redeem?  Is it as simple as that?  (If so, do any clients support this now?)

Or is there some additional software needed to create the combined address?  Can it be done without bringing the two private keys together?
This is basically correct. Your main challenge is that the current way to do multisig transactions references the public keys rather than just the addresses. Therefore when you generate the paper wallets, you need to take note of the public keys. Then you can input those into the bitcoin-qt console to generate the multisig address (there's a worked example by Gavin).

Note that using the funds in the multisig does not require the two private keys to exist together in the same machine, rather you just need to generate a signature using each (on separate machine).