This work presents a framework for developing a library of gaits for tensegrity robots, which are examples of highly non-linear, hyper-redundant, compliant systems. The first component corresponds to the design of a Central Pattern Generator (CPG) for such robots, which provides a reparametrization of the system that easily results in the generation of rhythmic gaits. Second, a novel framework is presented for simultaneously discovering effective gait parameters along different directions of motion. The framework integrates a parallel Bayesian Optimization (BO) process with classification. This integration is more efficient than Monte Carlo sampling or BO or classification alone. Evaluation is performed in simulation using a spherical tensegrity robot