To search backward in the history for a particular string, type
C-ssearches 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