Ctrl-r is what I use too. Usually requires fewer keystrokes than other methods discussed here. And it works for all commands in shell history.