[dcassett]

For non-fuzzy options:

I've found bash's history-search-backward and history-search-forward very useful. They complete commands that begin with what you have typed. I have them mapped to M-p and M-n.

I also find myself using bash's insert-last-argument command, which can be repeated to fill in the last argument of previous commands. I have it mapped to M-_.

Another feature I've been using is the dabbrev-expand function, which xterm (and some other terminals) have. This allows string matching on the terminal output including the scroll buffer. It's useful for forming a new command that uses previous arguments that are not last arguments, or that are outputs of previous commands. I have it mapped to M-/. I've tweaked the matching algorithm on my local xterm to allow tokens enclosed in quotes or braces (which programs often output) to be matched (xterm by default only considers non-whitespace).