What do I have to do before giving away my Ubuntu machine?

You normally have all your private data in /home, especially browser cache and so on.

You might have private internet-settings in /etc/Network-Manager. Visit /etc, and look into the directories. Reconfigure your things, delete private data (WLAN key), see if everything is vanished. If not, remove by hand. mc (midnight commander) is a useful tool to iterate through directories, to view and delete files. (shred, see bottom).

Another directory with private Data might be /var/spool or /var/cache. For example the cups-printer-spooler produces summaries of printjobs, and document name, date of job can be reconstructed. Maybe you wish to clean them too.

Those files in /tmp get automatically deleted on every startup. So if you didn't reorganized things, which only you may know,

• create a fresh new account without password for the new user, (who is prompted for a password on the first login) and give this user the right to become superuser. Look at your own profile to copy your privileges before deletion.
• login with the recover-option to get root access, and
  • cd /home/roflcoptr
  • find . -delete # or, instead of -delete, you might consider shred:
  • find . -execdir shred -n 1 {} +
  • control with ls
  • delete your normal account (see: /etc/passwd, /etc/shadow) (suggested from the comments, thanks @intuited, give him a star)

If you consider to clean empty space (@intuiteds second advice, maybe we should donate a star?), It would be more easy to use a live-cd to shred the whole system (which can continue unattended) and then install a new one (needs about 45 minutes with few interactions, mostly in the beginning). This could be in general the faster solution. More than one schred-iteration is nonsense.

Your safest option is to use something like DBAN to securely wipe the disk and then reinstall from scratch.

If you want to provide the same application profile to the recipient, you can use dpkg --get-selections to dump the system package state before wiping, and then use dpkg --set-selections after reinstallation to tell the new system that you want those packages installed. This will allow you to conveniently reinstall all the apps that you had set up.

The tool aptitude-create-state-bundle can also be used for this purpose, and is likely preferable, since it works at a higher level and can remember what packages were explicitly installed by you.

In my opinion, doing a complete disk wipe and reinstall of the OS is easier, less time-consuming, and more likely to erase everything that you wanted to erase. True, wiping the whole disk will take a long time, but you can go do something else while you wait. Removing specific packages and files from the existing OS is an involved process that requires lots of thinking and leaves lots of room for error. A complete reinstall accomplishes the same thing, only more effectively and with less work on your part.