Most people do Settings -> General -> Reset -> Erase all content and settings. But if you are overly concerned then I would restore in iTunes and set us as a new iPhone.
Prior to the introduction of iMessage in 2011, it wasn't necessary to do anything other than wipe the iPhone. Now failure to disable iMessage has the potential of being a big problem for the seller to correct. Much easier to just avoid the pitfall.
Devices that support hardware encryption (your 4s): Erases user settings and information by removing the encryption key that protects the data. This process takes just a few minutes.