Portions of this are copied from my answer to Scott's question.
This particular proposal only requires one change to Bitcoin: SPV proving.
SPV proving is required when you want to move Bitcoins from the sidechain to the mainchain. The idea is that rather than putting all of the rules to validate transactions on the other chain into the original Bitcoin client, Bitcoin clients would look at how much hashpower was used to secure the transaction. It's pretty clever, actually.
Destroying Bitcoins to fund other blockchains has always been possible.
One issue that I see is that I don't think there would be enough hashpower to secure the network from double spending; merged mining could probably fix that though.
Another weakness of the paper that I see is that it does not address what to do if someone does steal coins from the sidechain. (In other words, the Bitcoin network thinks there are 90 Bitcoins in the sidechain, but the sidechain thinks it has 100 BTC.) One possible approach would be to devalue all coins moved back to the mainchain by the percentage that was stolen. Another would be to take a flat percentage off the top of coins moved into the sidechain.