What is meant by gauge?

grintable's answer is close, but insufficiently general. Recall that in clical EM theory, we are primarily interested in the magnetic vector potential A because it's curl is the magnetic field B. That means you can add any vector function of position you want to A and still get the same B, as long as its curl is zero. The curl free component of A, then, identifies its gauge.