The efficiency of star formation governs many observable properties of the cosmological galaxy population, yet current models of galaxy formation largely ignore the important physics of star formation and the interstellar medium (ISM). To improve the physical description of star formation in hydrodynamical simulations of galaxies, we implement a new model for the ISM that includes low-temperature (T < 10^4 K) cooling, directly ties the star formation rate to the molecular gas density, and accounts for the destruction of molecular hydrogen by an interstellar radiation field from young stars. We use these simulations to study the relation between star formation and the ISM in galaxies and demonstrate that, for the first time, the new model simultaneously reproduces the molecular gas and total gas Schmidt-Kennicutt relations, the connection between star formation and disk rotation, and the relation between interstellar pressure and the fraction of gas in molecular form. We discuss the observationally verifiable predictions and potential implications of our results for dwarf galaxy formation and modeling, cosmological disk formation, and the luminosity and baryonic mass functions of galaxies. Throughout, we identify new areas for theoretical research into galaxy formation in the context of exciting forthcoming observational facilities that will probe the development of the galaxy population over cosmic time.