Designing soft robots poses considerable challenges: automated design approaches may be particularly appealing in this field, as they promise to optimize complex multi-material machines with very little or no human intervention. Evolutionary soft robotics is concerned with the application of optimization algorithms inspired by natural evolution in order to let soft robots (both morphologies and controllers) spontaneously evolve within physically-realistic simulated environments, figuring out how to satisfy a set of objectives defined by human designers. In this paper a powerful evolutionary system is put in place in order to perform a broad investigation on the free-form evolution of walking and swimming soft robots in different environments. Three sets of experiments are reported, tackling different aspects of the evolution of soft locomotion. The first two sets explore the effects of different material properties on the evolution of terrestrial and aquatic soft locomotion: particularly, we show how different materials lead to the evolution of different morphologies, behaviors, and energy-performance tradeoffs. It is found that within our simplified physics world stiffer robots evolve more sophisticated and effective gaits and morphologies on land, while softer ones tend to perform better in water. The third set of experiments starts investigating the effect and potential benefits of major environmental transitions (land - water) during evolution. Results provide interesting morphological exaptation phenomena, and point out a potential asymmetry between land-water and water-land transitions: while the first type of transition appears to be detrimental, the second one seems to have some beneficial effects.