How does the paper-based wallet work? More exactly - I know I can check the balance on, say, block explorer, but how do I send the bitcoins to someone when I have the private key?
You have to import the private key. You can do it with pywallet or in one of the online wallets, such as mtgox or blockchain.info.
Usually you use that as a savings wallet because it not practical to keep importing the keys somewhere (and it is safer if you keep it on the paper).