I have a jailbroken 3G. I was planning on restoring it to the original firmware, backing it up, and then restoring that backup to my iPhone 4. My logic was that this method would have the least chances of anything going wrong.
Although...
If I don't restore a backup, would all my apps and contacts still get synced to the new phone when I first plugged it in?