I am getting rid of my Samsung Galaxy S4 and want to know what steps I should take to make sure that private information has been deleted from the phone. I have removed the SD card and cleared all of the gallery files as well as music. What other steps can I take to make sure that the phone is as sterile as possible?
Remove the SD Card and SIM Card, and then do a Factory Reset.
If your device doesn't use full disk encryption, and you are worried about someone using advanced forensic tools to recover your data, you might want to overwrite the internal storage area with random data. You can do this by creating a file containing random data that fills up the entire free space. Once you've done that, do another factory reset.
If you've flashed and/or rooted your device, you would want to flash a stock ROM, and restore the default boot loader.
Make sure you've deregistered your phone from e.g. Google (especially Play), Facebook, Dropbox etc.
Encrypt the phone, optionally create a file full of random data that fills up all available disk space1, then factory reset. Repeat as many times as you like.
dd if=/dev/urandom of=random.txt bs=1G count=2, replacing
1G with however much space is left (credit)
Your best bet is to flash a factory image, maybe a more daunting task if you aren't familiar with it. However, check out sammobile.com for images and instructions, or YouTube of course.
In theory, with Android, a factory reset can tend to leave data behind: Ars article
With a system image, it effectively rewrites all partitions on the device, leaving it clean.