We report the discovery and characterization of a power-law correlation between the local surface densities of Spitzer-identified, dusty young stellar objects (YSOs) and the column density of gas (as traced by near-IR extinction) in eight molecular clouds within 1 kpc and with 100 or more known YSOs. This correlation, which appears in data smoothed over size scales of ~1 pc, varies in quality from cloud to cloud; those clouds with tight correlations, MonR2 and Ophiuchus, are fit with power laws of slope 2.67 and 1.87, respectively. The spread in the correlation is attributed primarily to local gas disruption by stars that formed there or to the presence of very young subregions at the onset of star formation. We explore the ratio of the number of Class II to Class I sources, a proxy for the star formation age of a region, as a function of gas column density; this analysis reveals a declining Class II to Class I ratio with increasing column density. We show that the observed star-gas correlation is consistent with a star formation law where the star formation rate per area varies with the gas column density squared. We also propose a simple picture of thermal fragmentation of dense gas in an isothermal, self-gravitating layer as an explanation for the power law. Finally, we briefly compare the star-gas correlation and its implied star formation law with other recent proposed of star formation laws at similar and larger size scales from nearby star-forming regions.