those instructions are for 3g, but it should work the same for 3gs:
If you've jailbroken your phone and you have SSH access:
The sounds are in /System/Library/Audio/UISounds/
They are aiff, rename them to .caf and replace as needed. You can listen to them with Quicktime or QuickLook to see what they are. You can replace the Mail Received one if you like, you can change any sound you want.