I think the pithy answer is that our eyes adapted to see the subset of the electromagnetic spectrum where air has no absorption peaks. If we saw in different frequency ranges, then air would scatter the light we saw, and our eyes would be less useful.
As previous answers have stated, the wavelength (or frequency) and intensity of the beam are important, as well as the type and amount of impurities in the air. The beam must be of a wavelength that is visible to humans, and fog or dust scatters the light very strongly so that you can see it. However, even in pure, clean air, you will be able to see a laser beam under certain conditions.
This is because light can scatter from air molecules themselves via Rayleigh scattering. Rayleigh scattering has a strong inverse dependance on wavelength, specifically $\lambda^{-4}$, so it will be easier to see with a green, and especially a blue, laser1. It also has a scattering angle dependance that goes like $1+\cos^2 \theta$, so it may be easier to see if your viewing angle is very close to the beam2.
With a 5mW green laser pointer, Rayleigh scattering is pretty easy to see. I imagine it would be even easier with blue/violet, but I'm not sure, since human eyes are most sensitive at green, so that may tip the balance. A more intense beam, like those used at night clubs or laser light shows, would be very easy to see if the beam were held still, but in those situations the beams are moving around rapidly to produce the light show, so Rayleigh scattering alone wouldn't really let you see much. In situations like night clubs, the scattering from fog produced by fog machines is much more important.
You are correct that, in space, because there is no atmosphere and nothing to scatter off of, you wouldn't see any sort of laser beam.
1: This is also why the sky is blue, incidentally.
2: DO NOT EVER TRY TO TEST THIS WITH A BEAM POINTED TOWARDS YOU If you want to try this out, take a laser pointer and hold it near your head (eg. against your temple) and point it away from you, in the dark.
Best Answer
Because Maxwell's equations are linear. Equivalently there is no elementary photon-photon interaction. If there were, say, a quartic photon interaction then you would be able to see a beam of light directly instead of seeing its interaction with dust particles.