IME, they're stored on device only. If you've ever moved phones this becomes painfully obvious unless you've setup backups to your personal Google Drive (native integration with app).

I'm not saying I believe their statement, but in principle they could be storing messages indexed by recipient and have the sender id be part of the encrypted content? Then you can drop messages in each user's inbox as they arrive, from which the user's app can read, but not have stored enough information to retroactively query "Show me everyone Alice has talked to"?