Animal locomotion typically employs several distinct periodic patterns of leg movements, known as gaits. It has long been observed that most gaits possess a degree of symmetry. Our aim is to draw attention to some remarkable parallels between the generalities of coupled nonlinear oscillators and the observed symmetries of gaits, and to describe how this observation might impose constraints on the general structure of the neural circuits, i.e. central pattern generators, that control locomotion. We compare the symmetries of gaits with the symmetry-breaking oscillation patterns that should be expected in various networks of symmetrically coupled nonlinear oscillators. We discuss the possibility that transitions between gaits may be modeled as symmetry-breaking bifurcations of such oscillator networks. The emphasis is on general model-independent features of such networks, rather than on specific models. Each type of network generates a characteristic set of gait symmetries, so our results may be interpreted as an analysis of the general structure required of a central pattern generator in order to produce the types of gait observed in the natural world. The approach leads to natural hierarchies of gaits, ordered by symmetry, and to natural sequences of gait bifurcations. We briefly discuss how the ideas could be extended to hexapodal gaits.