There's a recipe on webupd8.org for this. To prevent link rot, here's the important information (with a few additions).
sudo apt-get install trash-cli
This will install trash, empty-trash, list-trash and restore-trash commands, which you can use as-is or make rm an alias of trash (see below).
The semantic of the trash command is a bit different then the standard rm - it doesn't require -r flag in order to be able to delete directories. If this bothers you, webupd8.org proposes the following script, which you can put in your PATH and call it trash-rm:
#!/bin/bash
# command name: trash-rm
shopt -s extglob
recursive=1
declare -a cmd
((i = 0))
for f in "$@"; do
case "$f" in
(-*([fiIv])r*([fiIv])|-*([fiIv])R*([fiIv]))
tmp="${f//[rR]/}"
if [ -n "$tmp" ]; then
#echo "\$tmp == $tmp"
cmd[$i]="$tmp"
((i++))
fi
recursive=0
;;
(--recursive) recursive=0
;;
(*)
if [ $recursive != 0 -a -d "$f" ]; then
echo "skipping directory: $f"
continue
else
cmd[$i]="$f"
((i++))
fi
;;
esac
done
trash "${cmd[@]}"
In Ubuntu 12.04 and later, the last command in the script should be trash-put "${cmd[@]}" instead of trash "${cmd[@]}" (as the command has changed from trash to trash-put).
Then make the script executable:
chmod +x trash-rm
Once you have it in some directory in your PATH, add an alias to your ~/.bashrc, which will make bash to invoke your script instead of the actual rm command:
alias rm="trash-rm"
As djeikyb correctly points out, the .bashrc alias trick would only work for the user whose .bashrc is modified, and only in bash terminal session.
And that should be it.