For many organisms, searching for relevant targets such as food or mates entails active, strategic sampling of the environment. Finding odorous targets may be the most ancient search problem that motile organisms evolved to solve. While chemosensory navigation has been well characterized in microorganisms and invertebrates, spatial olfaction in vertebrates is poorly understood. We have established an olfactory search assay in which freely moving mice navigate noisy concentration gradients of airborne odor. Mice solve this task using concentration gradient cues and do not require stereo olfaction for performance. During task performance, respiration and nose movement are synchronized with tens of milliseconds precision. This synchrony is present during trials and largely absent during inter-trial intervals, suggesting that sniff-synchronized nose movement is a strategic behavioral state rather than simply a constant accompaniment to fast breathing. To reveal the spatiotemporal structure of these active sensing movements, we used machine learning methods to parse motion trajectories into elementary movement motifs. Motifs fall into two clusters, which correspond to investigation and approach states. Investigation motifs lock precisely to sniffing, such that the individual motifs preferentially occur at specific phases of the sniff cycle. The allocentric structure of investigation and approach indicates an advantage to sampling both sides of the sharpest part of the odor gradient, consistent with a serial-sniff strategy for gradient sensing. This work clarifies sensorimotor strategies for mouse olfactory search and guides ongoing work into the underlying neural mechanisms.