Spin noise spectroscopy with a single laser beam is demonstrated theoretically to provide a direct probe of the spatial correlations of cold fermionic gases. We show how the generic many-body phenomena of anti-bunching, pairing, antiferromagnetic, and algebraic spin liquid correlations can be revealed by measuring the spin noise as a function of laser width, temperature, and frequency.