There are two ways for quickly searching the history: Incremental search and plain string search. The good thing about both is that you only need to know part of the command you typed, in most cases three or four consecutive letters are enough.
Ok. Let's say you are SSHing into your other box regularly using the command ssh mylogin@myotherbox. Open a terminal and hit CTRL-R. The prompt changes to say "reverse-i-search". Start typing what you search for. Chances are that as soon as you have typed "s" and another "s", it will fill in the ssh command for logging into myotherbox. Hit Enter and it executes the command. If you don't want to, cancel the reverse i-search with CTRL-G. Whatever you started typing before the search will still be there, nice!
If you had happened to ssh into other boxes and didn't get the right result, you can press CTRL-R several times during the i-search to go to the previous occurence (towards the start of the history), or CTRL-S to search towards the end of the history. Note that CTRL-S is often bound to stopping the terminal, but that can be fixed by issuing stty stop ^Q, which rebinds stopping to CTRL-Q.
Bash also has a plain non-interactive search mode that can be entered using ALT-P, or ALT-N in the unlikely case you want/have to do a forward search. The prompt changes to a simple colon then and you can cancel as always with CTRL-G. Type a few letters and hit Enter. The first match will be filled in at the prompt but will not execute, which is great because you can edit it first this way.
Well, there is also a third very non-interactive way of search: Type a bang (exclamation mark) followed by what you search for. !ssh will likely result in this:
Useful for quickly repeating commands you use regularly, although dangerous if you don't exactly know what the bang-search will find and execute.