Living systems face the challenge of navigating natural environments shaped by non-trivial physical mechanisms. Notable examples are provided by long-distance orientation using airborne olfactory cues transported by turbulent flow, the tracking of surface-bound trails of odor cues, and flight in the lowest layers of the atmosphere. Terrestrial animals, insects, and birds have evolved navigation strategies that accomplish the above tasks with an efficiency that is often surprising and yet unmatched by human technology. Indeed, robotic applications for olfactory sniffers and unmanned aerial vehicles face similar challenges for the automated location of explosives, chemical, and toxic leaks, as well as the monitoring of biodiversity, surveillance, disaster relief, cargo transport, and agriculture. The interdisciplinary interplay between biology, engineering, physics, and robotics is key to jointly advancing fundamental understanding and technology. I shall review the above natural phenomena, then discuss the physics that constrains and shapes the navigation tasks, how machine-learning methods are brought to bear on those tasks, and conclude with the relevant strategies of behavior and open issues.