We consider the effects of different star formation criteria on galactic scales, in high-resolution simulations with explicitly resolved GMCs and stellar feedback. We compare: (1) a self-gravity criterion (based on the local virial parameter and the assumption that self-gravitating gas collapses to high density in a free-fall time), (2) a fixed density threshold, (3) a molecular-gas law, (4) a temperature threshold, (5) a Jeans-instability requirement, (6) a criteria that cooling times be shorter than dynamical times, and (7) a convergent-flow criterion. We consider these both MW-like and high-density (starburst) galaxies. With feedback present, all models produce identical integrated star formation rates (SFRs), in agreement with the Kennicutt relation. Without feedback all produce orders-of-magnitude excessive SFRs. This is totally dependent on feedback and independent of the SF law. However, the spatial and density distribution of SF depend strongly on the SF criteria. Because cooling rates are generally fast and gas is turbulent, criteria (4)-(7) are weak and spread SF uniformly over the disk (above densities n~0.01-0.1 cm^-3). A molecular criterion (3) localizes to higher densities, but still a wide range; for Z Z_solar, it is similar to a density threshold at n~1 cm^-3 (well below mean densities in the MW center or starbursts). Fixed density thresholds (2) can always select the highest densities, but must be adjusted for simulation resolution and galaxy properties; the same threshold that works in a MW-like simulation will select nearly all gas in a starburst. Binding criteria (1) tend to adaptively select the largest over-densities, independent of galaxy model or resolution, and automatically predict clustered SF. We argue that this SF model is most physically-motivated and presents significant numerical advantages in large-dynamic range simulations.