C-s moves forward in history, but you have to type it twice to begin with, once to toggle the mode, and once to actually move forward.

Backspace normally just deletes the last character in your incremental search string.

And be sure that C-s / C-q aren't set up for terminal flow control with something like:

    stty start undef stop undef