This paper considers the kinematics of hyper-redundant (or "serpentine") robot locomotion over uneven solid terrain, and presents algorithms to implement a variety of "gaits". The analysis and algorithms are based on a continuous backbone curve model which captures the robot's macroscopic geometry. Two classes of gaits, based on stationary waves and traveling waves of mechanism deformation, are introduced for hyper-redundant robots of both constant and variable length. We also illustrate how the locomotion algorithms can be used to plan the manipulation of objects which are grasped in a tentacle-like manner. Several of these gaits and the manipulation algorithm have been implemented on a 30 degree-of-freedom hyper-redundant robot. Experimental results are presented to demonstrate and validate these concepts and our modeling assumptions.