Because they're stored locally on your phone, and then encrypted as a backup file. The statement is saying that the messages aren't sent in the open, so no one (including Apple) can eavesdrop. Of course you can get them from your backup, if you have access to a password, you can always access encrypted data with it.
I'm not sure why that would be true.
I posit that such a system could work like this:
* An asymmetric keypair (e.g. RSA or ECC) is generated and stored on Apple's servers. The private key is encrypted with the user's password, which is not retained by Apple except in a hashed form.
* When a device is added, the private key is decrypted using the password and sent to the device.
* When your password is changed, either A) the private key is decrypted with the original password, and re-encrypted with the new password, or B) the private key is decrypted, used to decrypt all data, thrown away, and a new keypair is generated, with which all data is then re-encrypted.
It is, of course, obvious that Apple could, in theory, capture your plaintext password somewhere in there and use it to decrypt messages.
There are ways around this, such as devices doing the key decryption locally and only ever sending a derived/hashed form of your password to the server, and using a different derived/hashed form for encryption.
However, since you can log in to iCloud and Apple's store with your Apple ID in a browser, there is still no effective defense against Apple capturing your plaintext password (unless you care to perform a detailed inspection of a bunch of JavaScript every single time you load any content from Apple's servers).
Did your first comment not say what you meant?
> the private key is decrypted using the password and sent to the device.
wait, where is this private key coming from then? your other devices?
Remember, I'm only explaining a hypothetical method by which the Apple system could work, consistent with Apple's statements and behavior I've observed from my iPhones, iPads, and Macs. It's not an explanation of a strictly secure system.
where is it stored though?
http://support.apple.com/kb/HT4859?viewlocale=en_US&locale=e...
It doesn't state how the iCloud backup is stored however.
I don’t know, then, why when I do an iCloud restore on a brand new device, all existing messages are recovered. Is this a way to recover all past messages that’s not really addressed, if I can still recover all historical messages after replacing all devices connected to an iCloud account at once?
Cursory links:
http://security.blogoverflow.com/2012/09/qotw-34-imessage-wh...
https://github.com/meeee/pushproxy
http://imfreedom.org/wiki/IMessage