We present a new terrain classification technique both for effective, autonomous locomotion over natural, unknown terrains and for the qualitative analysis of terrains for exploration and mapping. Our straight-forward approach requires a single camera with little processing of visual information. Specifically, we derived a gait bounce measure from visual servoing errors that result from vehicle-terrain interactions during normal locomotion. Characteristics of the terrain, such as roughness and compliance, manifest themselves in the spatial patterns of this signal and can be extracted using pattern classification techniques. For legged robots, different limb-terrain interactions generate gait bounce signals with different information content, thus deliberate limb motions can effect higher information content (i.e. the robot is an active sensor of terrain class). Segmentation of the gait cycle based on the limb-terrain interaction isolates portions of the gait bounce signal with high information content. The decoding of, then sequencing of, this content from each cycle segment yields a robust classification of terrain type from known benchmarks. To extract this spatio-temporal pattern of the gait bounce signal, we developed a meta-classifier using discriminant analysis and hidden Markov model. We present the gait bounce derivation. We demonstrate the viability of terrain classification for legged vehicles using gait bounce with a rigorous study of more than 700 trials, obtaining 84% accuracy. We describe how terrain classification can be used for gait adaptation, particularly in relation to an efficiency metric. We also demonstrate that our technique is generally applicable to other locomotion mechanisms such as wheels and treads.