history + grep (or any other text searching command)
If you want to list all history entries containing string "foo":
history | grep "foo"
history - shows all commands in the history buffer
grep "foo" - searches for lines containing the string
foo, and you can also use regular expressions accordingly to manual of grep.
If you want to go back through history (like you did before with arrow keys) using ctrl+r is the way to go. Just press ctrl+r and start typing. You can press ctrl+r multiple times when the phrase is already typed and it will iterate back through matching history entries
This is my personal preference. Its solution is not vanilla out of the box, but I think it deserves some credit. You can install a fuzzy finder extension for bash and it will make searching for many things much more efficient (it replaces reverse i-search so ctrl+r is being used as a shortcut for searching in history).