The answer to this varies based on what your old and new devices are:
My old and new devices are both iPhones/iPads:
So long as you use the same account for the iTunes/App Stores, you can download the application for free. In addition, you will not have to reinstall the application or data at all, if you follow Apple's suggested upgrade procedure: http://support.apple.com/kb/HT2109
My old and new devices are both Androids:
So long as you use the same application store (Google Play, Amazon AppStore, etc) and the same account for that store, you will not have to pay again. To migrate your data, you will have to use the "Backup to SD Card" and "Restore to SD Card features of our Pro version apps, however.
My old and new devices are different (iPhone to Android, Android to iPhone, etc.):
The app stores for different types of phones are controlled by different companies. For example, Android Market is controlled by Google and Google Checkout, while Apple's iTunes is controlled by Apple. They do not have reciprocal agreements and as developers, we do not have the ability to transfer the license for an app across stores.
In addition, the apps can be quite different on different phones. We had to write the app, fresh, completely from the ground-up for each type of phone. Paying the nominal free for the app on different platforms helps us support development on that platform. You could think of it as being similar to blu-ray vs DVD. If you changed from a DVD to a blu-ray player, you'd normally have to purchase the same movie again for blu-ray even if you had previously purchased the movie on DVD. However, we do always offer a free version of the app that you can use. You might want to try it out first and if you like it on your new phone, then you can decide whether you'd like to upgrade.
Because the applications are so different, we do not currently have a way to move data to your new device, if you switch platforms.