invariant (Haar) measure
To 'average over a group' you need a fair way to weigh its elements — a notion of volume that does not favor any region. The Haar measure is exactly that: a way to integrate over a group that is unchanged when you slide everything by a fixed group element. It is the group-theoretic generalization of uniform measure on a circle.
Precisely, on a compact group G there is a unique probability measure mu (total mass 1) that is translation-invariant: for any fixed g and any function f, integral f(gx) dmu(x) = integral f(x) dmu(x), and likewise for right translation. Existence and uniqueness are guaranteed for compact groups, which is why O(n), SO(n), U(n), SU(n) all have a canonical 'uniform distribution'.
Its core use is AVERAGING. Given any object, integrate its group-translates against Haar measure and you get a group-invariant object: this single trick proves that every representation of a compact group preserves some inner product (so is unitary), and that invariant subspaces have invariant complements. Averaging over the group symmetrizes anything.
It is also how you sample RANDOM group elements: a Haar-random orthogonal or unitary matrix is the rigorous meaning of 'a uniformly random rotation', central to random matrix theory and to numerical algorithms that need an unbiased random basis. A caveat: for NON-compact groups (GL(n,R), SL(n,R), Sp(2n,R)) the total Haar mass is infinite, so there is no uniform probability distribution and left- and right-invariant measures can even differ.
The defining property: translating the integration variable by any fixed group element leaves the integral unchanged — perfect symmetry of the measure.
Concrete recipe for a Haar-random orthogonal matrix: fill a matrix with independent standard Gaussians and run Gram-Schmidt (a QR decomposition). The Q you get is uniformly distributed on O(n) — Vol I's QR procedure is secretly a Haar sampler.