And then ^o to execute that command, and put the next command from your history onto the command line ready for another ^o...

This works because you're in emacs mode, which gives you a bunch of other tasty shortcuts (http://www.scribd.com/doc/985254/Bash-Emacs-Editing-Mode-rea...) as well. There is an equivalent vi mode as well ("set -o vi").

Map <up> and <down> to do the same in .zsh:

  # search history on <up> key instead of paging previous commands:
  bindkey "\e[A" history-search-backward
  bindkey "\e[B" history-search-forward

and crl+r again for the next match. The ctrl+o tip didn't work for me though (OS X).

Thank you so much! No more `history | grep cmd` %)