Here are the docs for Vim's commandline history, also see this part of the docs on Vim's commandline history that covers the key bindings while in the history. It looks like you can say :foo and then hit the up arrow to find the last command that started with foo.
Type q: in the normal mode to open commands window. You can search/edit here using regular vim commands. You start in Normal mode. Press Enter to execute a command.
This approach lets you search across whole command not just beginning of line.
I was looking for this as well (finally after wondering why it wasn't built-in for some time) and decided I couldn't resist whipping up an implementation, so here you go: https://github.com/goldfeld/ctrlr.vim
It should work just like the shell's--well there are still a couple basic things missing (like pressing ^R again to skip to next match), but all that I use is in this first release, and I plan to add the rest in the coming weeks as I get time.
Press Ctrl+F in command mode to open the command history window. Then, you can use / , ? , and other search commands. Press Enter to execute a command from the history.
For more about the command history window, see :h cmdwin .