What makes the beam of some lasers:
visible? such as the ones used in clubs or such as the laser pointers sold at amazon which if pointed to the sky look like a solid visible beam of light crossing the sky (it reminds me of the lightsaber in Star Wars).
invisible? such as the ones used in pointers for presentations.
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.
The visibility is determined by three things:
Without dust or mist in the air you don't see any laser. It's the dust particles or mist droplets which reflect the light of the laser.
When you see a laser beam, what you are really seeing is the beam being scattered by various small particles suspended in the air. How well you see the beam will depend on how clear the air is, and on the ambient light levels the laser beam has to compete with.
In a night club, the air may have a high degree of smoke or other contaminants which will make the beam more visible, and the ambient light will be low, so they will stand out more. When people want to show off laser beams, they often add smoke or equivalent to the air.
Green colored lasers will also tend to stand out more, because the reception of the human retina peaks near that wavelength. Your "invisible" laser is probably a red colored laser operating in a brighter environment with clearer air. Take it into a dark smoke filled room and you will see it's beam just fine.
Here's an idea. Maybe it's kind of cheating, I don't know, you decide. Take a small diameter clear tube, fill with ordinary, unfiltered tap water and line the laser up to fire down the length of the tube. Seal the far end water tight. If you're firing the beam at a downward angle, you can leave the end closest to the laser open. The impurities in the water will make the beam pretty visible. Works great even with 10 mw HeNe (red) laser.
