Best way to search through shell's history

Ctrl+R is usually the best way, as descriptor said. You can also use !string, which runs the most recent command starting with string, or !?string?, which runs the most recent command that contains string.

_{(I think that's the only stuff relevant to this question, but I covered much more of the history commands in this answer)}

When using Bash, type Control-R and then start typing. Typing Control-R repeatedly after inputting some text will move you back in matching command lines.

Not sure if this will help, but I like to use ctrl-r and then start typing the command. It should go through your history and present you with the first match. To toggle through the matches just hit ctrl-r again.