In this dissertation we present the results of a five-year-long radial velocity planet search and a companion survey of detailed stellar abundances. The Solar Twin Planet Search is a uniquely designed observing program on the HARPS spectrograph that aims to characterize the planetary systems of 68 solar twin stars. As we demonstrate in this work, solar twins' chemical compositions can be spectroscopically determined at an unparalleled level of detail. My thesis pairs these precise stellar abundances with information about the stars' planetary systems to give new insights into the connection between stars and the planets they form. Knowledge of stellar composition can give a glimpse into the history of planetary systems. In the HIP 11915 system, we have discovered a planet of comparable mass and orbital period to Jupiter around a star with an abundance pattern indistinguishable from the Sun's. The HIP 68468 system, on the other hand, is vastly different from our own, with two close-in planetary companions and a stellar composition that could indicate past accretion of planetary material onto the host star. In addition to these planets discovered through our Solar Twin Planet Search, we also present a new analysis of Kepler-11, whose six planets are widely regarded as the archetypal "puffy" close-in exoplanets. Contrary to previous studies, we identify Kepler-11 as a solar twin. The revised stellar properties and new analysis raise the Kepler-11 planet densities by between 20-95% per planet. These individual systems demonstrate the power of combining stellar characterization with planet detections. The true potential of the Solar Twin Planet Search goes beyond single systems to characterize a statistically significant population of solar twins. We present photospheric abundance measurements of 17 elements in 80 solar twins using co-added HARPS spectra for precisions on order 0.01 dex (~2%). From this large sample of solar twins, we investigate the dependence of stellar composition on age and other characteristics. We present unprecedentedly precise galactic chemical evolution trends. We also find a much smaller dispersion in the C/O and Mg/Si abundance ratios than previously reported in non-twin-star studies and discuss the implications of this result on the compositional diversity of planets throughout the galaxy. Finally, we demonstrate that the Sun is depleted in refractory materials relative to 92% of solar twins, hinting at an atypical history of dust condensation in the solar system. While the cause of this trend is not definitively determined, we conclude with a vision of future studies which will shed further light on the connections between detailed stellar compositions and planets.