Tensegrity-based robots can achieve locomotion through shape deformation and compliance. They are highly adaptable to surroundings, have light weight, low cost and high endurance. Their high dimensionality and highly dynamic nature, however, complicate motion planning. So far, only rudimentary quasi-static solutions have been achieved, which do not utilize tensegrity dynamics. This work explores a spectrum of planning methods that increasingly allow dynamic motion for such platforms. Symmetries are first identified for a prototypical spherical tensegrity robot, which reduce the number of needed gaits. Then, a numerical process is proposed for generating quasi-static gaits that move forward the system's center of mass in different directions. These gaits are combined with a search method to achieve a quasi-static solution. In complex environments, however, this approach is not able to fully explore the space and utilize dynamics. This motivates the application of sampling-based, kinodynamic planners. This paper proposes such a method for tensegrity locomotion that is informed and has anytime properties. The proposed solution allows the generation of dynamic motion and provides good quality solutions. Evaluation using a physics-based model for the prototypical robot highlight the benefits of the proposed scheme and the limits of quasi-static solutions.