Deleting info on cell phone? (They're computers to me!)

Howdy folks...
(Yep...this thing is so much like a computer to me I figgered this is the best place to ask!)

I've decided to get rid of my cell phone (Ebay here I come!). I guess it is best to remove my contacts list and have figured out how to delete them. However, is there anything else I need to do before I sell this? I don't know if there is a "storage" system on the phone where the eventual owner can pull up my deleted contacts or not.

Is there anything else I should consider doing before I sell? Take the battery out? (Will that get rid of any stored info?)

Many thanks!
Shoe.