I have iCloud set up on all three devices, but email messages deleted on one device don't also get deleted on other two devices. How do I fix this?
I haven't seen iCloud fail like this other than when there is an outage for the server hosting my mail. You could check for this by disabling mail on all devices and then re-enabling it so that whatever is present on the iCloud mail server syncs down to each device in turn. You might also power off each device when iCloud mail is off to ensure any cleanup scripts run at boot to clear any caches, but I've not seen this to be needed in experience so far.
Worst case, you would need to open a ticket with iCloud support if the things you can control (like enabling / disabling / rebooting and if needed, restoring the devices) fails to remedy this sync issue.