The ability to leverage a body's physical properties to robustly interact with and exploit its environment is an important trait of biological intelligence. This principle of physical, or embodied intelligence, plays a significant role in advancing robotics, particularly for systems operating in fluidic environments where a robot's compliant morphology, sensing, and control are tightly coupled with the surrounding medium. This thesis introduces methodologies on how compliant underwater robots, ones which are bio-inspired by fish, squid, or octopus, can be designed, controlled, and assessed to become faster, more efficient, and more robust by leveraging fluid-structure interactions. In addition, it also introduces methods using large-scale robotic experimentation setups where designs of soft structures, such as paper airplanes and flags, can be optimized given the fluid environment. Taking a data-driven and experimental approach, I have developed robotic systems and methodologies that enable the demonstration of five key results. Firstly, a design methodology and mechanism are presented for the spatio-temporal exploitation of variable stiffness in soft underwater robots. This work demonstrates how a robot can modulate stiffness in real-time and use asymmetric structures to improve propulsion. Secondly, proprioceptive sensing mechanisms and materials are integrated to enable state estimation. This shows how mechanoreceptive voids and hydrogel-based sensors can be used to accurately estimate a robot's pose and deformation for closed-loop feedback. Thirdly, a low-complexity, compliant fish-like robotic platform is developed for the systematic exploration of diverse morphologies. This scalable platform allows for the investigation of how performance metrics like thrust and efficiency trade-off across different body sizes. Fourthly, directed, large-scale experimentation and learning-based optimization are leveraged to search and explore high-dimensional morphology design spaces. A methodology is presented for the automated optimization of complex behaviors, from paper airplanes to flapping flags, by combining physical experiments with probabilistic models. Lastly, the principles of embodied intelligence are extended into a high-level framework that translates these methodologies into actionable strategies for the design, control, and communication for robots and beyond. These results, when combined, represent a holistic contribution to advancing soft robotic systems that leverage their compliance and morphology to actively exploit fluid environments for intelligent and adaptive interactions.