I have an Android phone which I just sold on eBay. What measures should I take before posting it off to its new home? Please answer thoroughly!
Ensure you have a backup of any information on the device that is crucial to you.
There is a wide range of ways to achieve this, from "cloud" synchronization, to apps, to command line tools. For example, at least in some cases, the Cyanogenmod project recommends using the Android Debug Bridge to back up an Android device to a PC:
adb backup -apk -all -f backup.ab
You should research the options available and apply a method for backing up that meets your needs.
Protect your privacy
Based on these articles from Greenbot, ArsTechnica, Digital Trends, LifeHacker, and (ahem) Reddit, the three persistent storage devices you should remove or securely erase if present, before relinquishing an Android device to an untrusted party, to prevent that party accessing potentially sensitive data on the device, are:
External storage (e.g. an actual, removable microSD card).
Internal storage (aka "Internal SD card", even though it's not really an SD card).
The SIM card and the external storage are easy to deal with: remove them from the device before handing over the device.
A factory reset reformats the phone's user-data partition, but it's not a "secure" wipe; it doesn't overwrite everything with zeroes. If you want to be sure everything is erased, you can encrypt the phone first (which overwrites all the data with encrypted versions of itself), then do a factory reset (which sets up a new unencrypted filesystem).
Note that a factory reset leaves the phone's system partition (the "ROM") untouched. If you've made any changes to the system partition (such as rooting), those will remain.
That's all very well if your Android phone supports encrypting the internal storage. If not, then you had better either gain shell access to the device and perform something like
cd /data && cat /dev/urandom > 0, or just not relinquish your device to an untrusted party.
You may wish to back things up in the first instance in which case I would recommend My Back Up Pro.
In order to perform a Factory Reset please read this small tutorial written by Oliver Hill on May 11th 2012 entitled "How to perform a factory reset on your Android phone" for Little Green Robot Publishing (who publish a monthly magazine called The Android Magazine in the UK)
People in the past have recommended to myself that when performing a Factory Reset it should be carried out twice (whether this is necessary or not i am not sure, but there is no harm in doing it.)
If you have an HTC device and you are really worried, you can fully format the SD card, run the RUU for the stock software, and then boot in to Android, format the SD card, and factory reset once and shut off (so that the person who turns on the phone is greeted by the first-time setup). That's what I would do.
Not mentioned by the other answers: remove Google accounts from the phone before factory resetting, if you factory reset from recovery. Google's factory reset protection (FRP) is an anti-theft measure that requires a previous Google account's password to use a phone. Removing Google accounts disables this security feature so the buyer can install new accounts without prior passwords.
If you don't remove accounts to disable FRP, you end up with this problem.