On a standard Ubuntu install: If you press ^R after already typing part of what you're searching for, and then press a key (space, or more of the command you're searching for), then it'll switch to the history-search mode with that value pre-filled in.