A gauge transformation in physics involves some kind of mathematical change to a physical theory that does not affect the physics of the theory. This is different from the notion of symmetry in physics.
A symmetry transformation is an
invariance in the system
under some kind of physical change. A
gauge transformation is purely mathematical, reflecting that the mathematical construction of your theory contains nonphysical (i.e. unmeasurable*) information. Here are some of the simpler examples of gauge transformations:

1. Adding a constant to the energy of a system: E → E + ΔE. Physical measurables only depend on changes in energy, not in the actual zero-point, which we are free to choose. The total energy of a (noncosmological) system is unmeasurable; only changes in the energy are measurable. Adding a constant will not change these measurements.

2. In quantum mechanics, multiplying a wave function by a (constant) phase: ψ → e^{iθ}ψ. All physical observables depend only on the magnitude of the wave function, and perhaps how its phase changes with respect to some variable: ψ*Xψ, where X is some linear operator. No physical experiment could be done to measure, say, the imaginary part of the wave function. Its particular direction in the complex plane is our choice; all that matters is how different phases vary and interfere. The actual value of the phase has nothing to do with any real physics. In quantum mechanics, applying our first example of a gauge transformation is mathematically equivalent to a phase shift.

In contrast some examples of possible symmetries of a system might be rotational symmetry, translational symmetry, Lorentz invariance, reflection symmetry, charge conjugation symmetry, time-reversal symmetry, etc.

When someone uses the phrase “gauge transformation”, they are almost always talking about the example from electromagnetism. Electromagnetism deals primarily with two vector fields: the electric field, **E**, and the magnetic field, **B**. Since each of these vector fields have three components, it’s very much like solving coupled equations for six different variables. In general, this can be a pain in the neck.
However, this becomes radically simplified when one
introduces the scalar potential, V, and the vector potential, **A**. If one can solve the equations for these quantities, one can directly calculate **E** and **B**. This is handy, because since V is a scalar, we’re now only working with four variables.

The equations that directly relate them
are:

**E** = -**Grad**(V) – d**A**/dt

**B** = **Curl**(**A**).

As promised, this is an example of gauge invariance; the gauge transformation in electromagnetism is:

**A** → **A** + **Grad**(λ);

V → V – dλ/dt.

For any function λ(x), applying this transformation will not affect **E** and **B** (to see this, one must note that **Curl**(**Grad**(λ)) = 0 for all λ). Since **A** and V were just mathematical constructions to make our lives simpler, they are
not measurable functions. Their value at some given point has no real physical meaning.
Thus this transformation has no physical meaning. However, it *can* be used to make our calculations simpler. Your particular choice of gauge usually depends on what equation you want to simplify. It often involves making some term vanish, or causing two terms to cancel. The two main examples of gauge choices in electromagnetism are:

Coulomb Gauge: Pick λ such that Div(**A**) = 0.

Lorentz
Gauge: Pick λ such that Div(**A**) = -μ_{0}ε_{0}dV/dt.

There are other examples of electromagnetic gauge choices which are used in quantum field theory, namely Feynman Gauge and Unitary Gauge, but I'm not going to talk about quantum field theory today.

In General Relativity, gauge transformations are equivalent to isometries of spacetime: coordinate transformations that don't change the intrinsic geometry of the space in question. The intrinsic geometry of spacetime is all that is needed to calculate the physics; how this geometry is represented does not have any physical signifigance.

Gauge transformations are physically meaningless, but interestingly enough, this makes them a powerful physical tool. Mathematical quantities that correspond to physically meaningful information must be invariant under gauge transformations. This means we have a method for determining what kinds of questions are meaningful to ask physically; questions which can be experimentally tested and answered must not depend on our choice of gauge. This can dramatically narrow down the scope of questions which we can ask.

*Unmeasurable meaning physically undetectable; not to be confused with the common usage of "unmeasurable" in quantum mechanics, to describe the notion that a particle can't be pinpointed with a certain position and momentum simultaneously (did I just use the word "simultaneously?"). This idea, in truth, has nothing to do with measurement, but that's a discussion for another day.