You can do this one of two ways:
First Way: Sync and re-setup the phone:
First, connect your old phone. Make sure that you sync contacts to something like outlook or GMail or Mobile me. Copy off photos( these won't go back on the camera roll of your new phone, you'll need to tell iTunes to sync this folder to your new phone and it will be a photo album )
Now, on your old device go to Settings -> Erase All Content and Settings, take it into Apple and they'll give you your new device and put the existing sim into your new device. Go home, connect your phone, and sync. All your apps, contacts, etc will copy over. You'll have to re-setup mail accounts, wifi logins, etc. You will lose app saved data and game saves.
Option 2: Restore from backup.
With your old phone, connect it to iTunes, and right click on the iPhone within iTunes and choose "Backup". After the backup is done, disconnect your phone, go to Settings -> Erase All Content and Settings. Go to Apple, likely the phone will still be erasing the data, that's fine, they will still take it in. They will give you your new device, with your old sim and set it to activate. From there just go home, plug-in your iPhone. iTunes will recognize it, right click on the iPhone in iTunes and choose "Restore From Backup...". This will restore ALL your previous settings, mail, app data, etc. You'll have to re-enter Wifi and Mail Passwords, but it will remember all the other settings.
The choice is yours.