It seems like a toy compared to most of the other tools in this thread, but FWIW I have a little script I call "did":
grep "$1" ~/.bash_history | tail
It just shows me the last ten commands that include a search term. E.g. "did foo" shows the last ten commands that include "foo".