You can search forward as well. From the bash info manual, “8.2.5 Searching for Commands in the History“:
To search backward in the history for a particular string, type
C-r. TypingC-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
stty -ixon