We present experiments on polarization gradient cooling of Ca$^+$ multi-ion Coulomb crystals in a linear Paul trap. Polarization gradient cooling of the collective modes of motion whose eigenvectors have overlap with the symmetry axis of the trap is achieved by two counter-propagating laser beams with mutually orthogonal linear polarizations that are blue-detuned from the S$_{1/2}$ to P$_{1/2}$ transition. We demonstrate cooling of linear chains of up to 51 ions and 2D-crystals in zig-zag configuration with 22 ions. The cooling results are compared with numerical simulations and the predictions of a simple model of cooling in a moving polarization gradient.