Q:

What do they mean by 'This amp has a lot of headroom'?

Do they mean how loud it will go without getting distortion?

A:

I'd further qualify what ledfloyd has said: headroom defines the level you can obtain before the signal starts "clipping", that is: before the peaks begin to flatten out and resemble a square wave (the sound of which we call OD/distortion).
Once your signal's clipping, not only does it distort, it compresses somewhat as well (due to the fact that you get less room between the peak level and the average level - hence the name). Once you run out of headroom, you start to lose dynamics as well.

A:

"Headroom" refers to how loud you can turn up an amp (usually a referring to a non-Master Volume Tube amp) before it starts to break-up into Distortion/Overdrive.

