http://www.gnu.org/software/bash/manual/html_node/Searching.html
To search backward in the history for a particular string, type
C-r
. TypingC-s
searches forward through the history.
The problem with Ctrl-S however is that sometimes collides with XON/XOFF flow control (in Konsole for instance). The searching is a readline feature however, and you should be able to bind it to some other key.
Update: Simpler and better is just to disable XON/XOFF by running
stty -ixon