On my Ubuntu 20.04 server I cleverly installed this reverse search program... but I have no idea what it is called!
Being able to easily see multiple options while going through command line history (by pressing Ctrl+R) is nice, so I would like to know the program's name.
This is probably fzf, a command line fuzzy finder ("fzf" stands for "fuzzy finder").
It is a great command line tool that allows searching for files, folders, command history, etc, using approximate string matching or fuzzy matching (hence the name). Here is a screenshot of how the recent history looks on my terminal by pressing Ctrl+R (the same as yours):
Being a fuzzy matching tool means that you don't have to type exactly the name of the object you're looking for, but typing some characters of the object's name should be enough in many cases to yield the expected result. The tool is also interactive, meaning that the results are generated as you type.
Many projects make use of fzf. Here is a list of such projects: https://github.com/junegunn/fzf/wiki/Related-projects