1. Sync the iPhone to the Macbook (this will make sure all your contacts are in the Address Book & appointments are in iCal)
2. Go into iTunes and select 'Restore' - This will wipe the iPhone clean and set it up as new (Make sure once its done restoring that you select SET UP AS NEW PHONE and don't restore an old backup)
3. Power down the phone and pop out your sim from the top (use a paperclip to open the Sim Tray)
4. Sell the phone, profit!
And yes, you need to remove your sim before you sell it. Its tied to your account and is basically your phone number. When you buy a new phone, you can just pop the sim in and be on your merry way. Thats the great thing about GSM phones, you can move your phone number with you to any compatible phone or even pick up a local number when your traveling internationally and use your current phone.
As I mentioned earlier, Unlocked phones carry a higher price tag, but I wouldn't recommend it doing it yourself if your not too familiar with the process. Currently the iPhone is locked to AT&T, so only AT&T sim card work inside the phone. Unlocking allows you (or anyone else) to use the iPhone on any GSM carrier, not just AT&T.