This particular proposal only requires one change to Bitcoin: Simplified Payment Verification (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.
The sidechain proposal described in that paper glosses over the changes to make SPV proofs work:
To use Bitcoin as the parent chain, an extension to script which can recognize and validate such SPV proofs would be required. At the very least, such proofs would need to be made compact enough to fit in a Bitcoin transaction. However, this is just a soft-forking change, without effect on transactions which do not use the new features.
It would be more than an extension to script. Script currently has no way of looping or signaling to other scripts, which you would need. I'm pretty sure this would require a hard-fork. (Could someone more familiar with Bitcoin's internals chime in here? Could adding looping/signalling be done without a hardfork?)
I think it would make a lot more sense to not track the UTXO's of the coins moved to the sidechain at all, and just keep a running total. Then, have a hardcoded validator for each sidechain.
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.
