How do you search through Vim’s command history?

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.