Tensegrity robots, which combine both rigid and soft elements, provide exciting new locomotion capabilities but introduce significant control challenges given their high-dimensionality and non-linear nature. This work first defines an effective parameterization of a spherical tensegrity for generating rhythmic gaits based on Central Pattern Generators (cp G). This allows the definition of periodic and rhythmic control signals, while exposing only five gait parameters. Then, this work proposes a framework for optimizing such gaits by exploring the parameter space through Bayesian Optimization on an underlying Gaussian Process regression model. The objective is to provide gaits that allow the platform to move along different directions with high velocity. Additionally, kNN binary classifiers are trained to estimate whether a parameter sample will result in an effective gait. The classification biases the sampling toward subspaces likely to yield effective gaits. An asynchronous communication layer is defined between the optimization and classification processes. The proposed gait discovery process is shown to efficiently optimize the parameters of gaits defined given the novel CPG architecture and outperforms less holistic approaches and Monte Carlo sampling.