Imported from the Apple Support Forums via the Wayback Machine 🔗
That depends on how you are using iCloud. If you are using Messages with iCloud, then yes they are stored in iCloud, but they are also on your device. That being said, whatever you see on your device is what is in iCloud. Messages with iCloud keep all of your devices in sync with regard to those messages, but as a result of that, if you delete a message on one device, you delete it everywhere including in iCloud.
If you backup with iCloud, but do not use messages with iCloud, then the messages are stored in the backup. The only way to see those messages is to restore the backup which restores everything in that backup back onto your device.