When using a paper wallet and doing partial spends via blockchain.info. Where does the change go? I'm pretty shocked that I found out now about the change thing as I read everywhere about paper wallets being secure, but no where does it state that when you spend partial amounts from your paper wallet you might actually lose it all if you don't have a change address setup.

Now my question is how does blockchain.info handle this paper wallet situation with change addresses? It's kind of scarey knowing that you coins can just disappear just because you don't know the inner workings of how transactions work.
If you use a paper wallet with just one address. The most common way to make transactions that do not spent a complete unspent output (UTXO) is to send the change back to the wallet address itself. 

Note that using only a single address implies that you have no privacy whatsoever. Everyone that Evers comes to know your address can see your balance and every transaction you receive or send. 

Paper wallets are useful to safely and conveniently store some bitcoins, but when you want to make payments on a more frequent basis, you should use a more sophisticated wallet that can contain multiple addresses. 

Note that HD wallets (Hierarchical Deterministic wallets) make it possible to have a paper wallet that can consist of many addresses. However I don't know of a wallet app that already supports this type of wallets today.