This paper describes practical, effective approaches to stereo perception and dead reckoning, and presents results from systems implemented for a prototype lunar rover operating in natural, outdoor environments. The stereo perception hardware includes a binocular head mounted on a motion-averaging mast. This head provides images to a normalized correlation matcher, that intelligently selects what part of the image to process (saving time), and subsamples the images (again saving time) without subsampling disparities (which would reduce accuracy). The implementation has operated successfully during long-duration field exercises, processing streams of thousands of images. The dead reckoning approach employs encoders, inclinometers, a compass, and a turn-rate sensor to maintain the position and orientation of the rover as it traverses. The approach integrates classical odometry with inertial guidance. The implementation succeeds in the face of significant sensor noise by virtue of sensor modelling, plus extensive filtering. The stereo and dead reckoning components are used by an obstacle avoidance planner that projects a finite number of arcs through the terrain map, and evaluates the traversability of each arc to choose a travel direction that is safe and effective. With these components integrated into a complete navigation system, a prototype rover has traversed over 1 km in lunar-like environments.