Gait generation is very important as it directly affects the quality of locomotion of legged robots. As this is an optimization problem with constraints, it readily lends itself to Evolutionary Computation methods and solutions. This paper reviews the techniques used in evolution-based gait optimization, including why Evolutionary Computation techniques should be used, how fitness functions should be composed, and the selection of genetic operators and control parameters. This paper also addresses further possible improvements in the efficiency and quality of evolutionary gait optimization, some problems that have not yet been resolved and the perspectives for related future research.