They claim end-to-end encryption, which means they don't store it unencrypted.

From a wired article about it:

"Textsecure has actually already been quietly encrypting Whatsapp messages between Android devices for a week. The new encryption scheme means Whatsapp messages will now travel all the way to the recipients? device before being decrypted, rather than merely being encrypted between the user?s device and Whatsapp?s server."

That doesn't mean they (Whatsapp) don't have decryption keys either.

If it was stored on their server I would assume I would be able to get my old messages when I change phone but it didn't happen last time I did, plus they could have implemented web also for iOS without relying on your phone to show messages in the browser (through more permissive android functionality), no?

Well they don't need to store your whole message, once they have processed it and updated their profile database with whatever is of value to them they will most likely delete it. They should all happen within minutes if not seconds of you sending the message.

I believe messages pass through the servers, but once a message makes it to your device, its online copy gets deleted.