A little more information I dug up, plus another question...
Based on various reports, if you backup the old phone and restore to the new phone, the applications and their data come with it. Here's Apple's knowledgebase article on backing up and restoring:
http://support.apple.com/kb/HT1414
Plus a key quote from that KB article: "Restoring from backup is different from performing a full software restore. Restoring from backup restores the settings, application data, and other information saved in a previous backup."
The key is to not just do a normal sync (which just syncs applications but not data), but instead restore from backup.
So, I think a key question is whether or not users will have to upgrade their old phone to iOS 4 before doing a backup and restore to the new device, or if the new device will take the backup without having first done the backup from another iOS 4 device.
Aaron