Press Ctrl-R, and you can do an incremental search through your command history. Ctrl-R goes forward through the found entries, and Ctrl-Shift-R goes backwards.

Or, if you use fish like me, it does it automatically.