Personally I've bound history searches to the up/down arrow to make bash behave more like the C-shell in this regard:

    "\e[A": history-search-backward
    "\e[B": history-search-forward

(This was really the only thing I disliked about bash compared to csh, so imagine my delight when I found out this option existed in readline.)