The computer graphics community has made great advances in rendering the visual appearance and dynamic motion of real world phenomena, but relatively little has been done to render the sounds we hear with the same amount of plausibility and realism. While pre-recorded sounds may give the best results for pre-rendered movies, this is not a satisfying approach for real-time, interactive applications. In order to provide plausible sounds for interactive virtual environments, automated methods synchronized to visual simulations must be developed. In the past couple of decades, there has been increasing interest within and outside the graphics community to tackle this problem, and many techinques, such as linear modal models for rigid body sounds, have been successfully developed. This thesis presents new methods which advance the state of the art by making automated, realistic sound synthesis more practical for a wider range of physical phenomena. In particular, it introduces techniques for two types of nonlinearly deformable bodies: thin shells and cloth. Thin shell objects, such as trash cans and plastic water containers, do not deform very much visually, so their appearance and motion may be well approximated as rigid bodies. However, they are still significantly more flexible than solid objects, and this greatly affects the sounds they produce. Linear modal sound models are no longer sufficient. Due to the nonlinaer nature of their deformations, the modes do not vibrate independently, and thus a more sophisticated dynamics model is needed to integrate their audible motion. This thesis first introduces cubature optimization as a method for simulating nonlinear reduced deformable models in general, and then it shows how it can be used to enhance modal models for practical synthesis of thin shell sounds. Beyond the computational costs, modal models also require rather large memory costs at run-time, as all vibrational modes must be accessible. These modes can be compressed by very large amounts, and methods for doing so are presented as well. Finally, another type of highly deformable body is cloth. Cloth has been well-studied by the computer graphics community, and this thesis presents a practical method for synthesizing sounds synchronized to cloth animaitons. Unlike the case of thin shells, this method is largely data-driven, as cloth is a much more complex material. Existing cloth simulation techniques, while successful in producing convincing visual motion, cannot practically model all the subtleties of cloth structure which greatly affect the resulting sound. Instead, we use a database of recordings with a motion-driven synthesis pipeline to synthesize plausible, natural-sounding results.