Over the long weekend, Apple posted a handy support document that explains how to replace your original iPhone with a new 3G iPhone. Basically there are two tracks:

1). In the US you don’t need your original SIM as your original “account information will be transferred to iPhone 3G’s included SIM when you purchase iPhone 3G.”

2). Outside the US, “you can use your original iPhone’s SIM with iPhone 3G.”

Once your transfer is complete, all you have to do is back up your original iPhone to iTunes 7.7 and then restore that backup to the new iPhone 3G. This should transfer all your saved SMS messages as well as email accounts, notes, etc. Once that’s done, you should probably erase the old iPhone with the new secure erase option.