Create ~/.inputrc and fill it with this:

"\e[A": history-search-backward
"\e[B": history-search-forward

This allows you to search through your history using the up and down arrows … i.e. type "cd" and press the up arrow and you'll search through everything in your history that starts with "cd".

It's a little bit like ctrl-r (mentioned in many of the comments below), but anchored to the start of the line, and the arrow keys allow you to scroll back and forth between matches.

I use it when I'm looking to (for instance) call up the last ping I did (hit p, up arrow, return), whereas I use ctrl-r more like search, when I'm trying to find a command based on an argument or option that I used.

Both useful.

Other options that I find useful to add:

set show-all-if-ambiguous on

This alters the default behavior of the completion functions. If set to ‘on’, words which have more than one possible completion cause the matches to be listed immediately instead of ringing the bell. The default value is ‘off’.

set completion-ignore-case on

If set to ‘on’, Readline performs filename matching and completion in a case-insensitive fashion. The default value is ‘off’.

(as miah points out below, this is all actually Readline functionality. The title should be "Readline is the single most useful thing in everything" ;)