Yes, back up your phone via iCloud and possibly through iTunes, then just go into iCloud settings and turn off find my iPhone. Finally, erase all content and settings.Also do you delete the data off your phone yourself or do the folks at the store handle that?
Also I'm assuming you need to back up everything up on Cloud first so you can transfer it to the new phone right?