EDIT [missed the edit window] whoops, I see ctrl-r is "reverse-search-history" (not "history-search-backward"), it matches your input to any part of the history (so the prefix issue doesn't arise). So you could just type the hostname, and it will pick out the most recent line in the history that matches - it needn't be at the beginning of the line. You can hit ctrl-r again to go to a matching line further up.

ctrl-s goes back down again, but not working for me, apparently because my gnome terminal intercepts it before bash's readline sees it, using it for xon/xoff according to http://stackoverflow.com/questions/791765/unable-to-forward-... This "fixes" it (by disabling the STOP feature of the terminal), so ctrl-s works to search down.

  stty -ixon

Honestly, simply reading `man bash` from start to finish was one of the best things I ever did. I started doing it with all sorts of stuff. May I suggest you start with `man man`?

Then someone told me about `apropos` which is summarized in it's man page as "search the whatis database for strings". Sooo useful. Not nearly as useful as simply reading man pages from start to finish, but I've only got so much spare time.

generalize to gnu/linux tools.