Whenever you log in to your account on an Android device, it will download everything from the web to the device. First, confirm that you can see those messages on the web. If you can't, then you deleted them at some point using the "Danger Zone" option on your phone. If you still have the messages on your phone, you can go to the "My Account" section on the phone and use the "Refresh Account" option to push them back up to the web.
If you can see the messages on the web, you will be able to download them to the new device. You can just clear the app data (or uninstall and re-install) the app to start the download process again.