Backup your iPhone 3GS in iTunes, then restore that backup to your 4S:
1. Disable automatic syncing on connection in iTunes Prefs > Devices > Disable....
2. Connect the 4S and right-click the divice tab (left border of iTunes window) and select "Restore from backup." You should see a list with a choice of the 3GS backup. You may not, then have to do a full restore by selecting "Restore" on the 1st page, then chosing to use the backup in the last stage. This will also update the phone to iOS 5.1.
iOS 5.0.1 - Jailbroken? If so, a full restore will partially remove the jb, and possibly fail with error 1015 or 3194.
Message was edited by: modular747
Each device has its own backup. Backing up the 3GS won't delete the 4S backup. However, you want to add the new contacts on the 3GS to the 4S and what I suggested won't do that. Unless you've been syncing those contacts to an app on your computer or cloud service, you'll have to do it manually.