We show that the symmetry algebra governing the interacting part of the matrix model for M-theory on the maximally supersymmetric pp-wave is the basic classical Lie superalgebra SU(4|2). We determine the SU(4|2) multiplets present in the exact spectrum in the limit where mu (the mass parameter) becomes infinite, and find that these include infinitely many BPS multiplets. Using the representation theory of SU(4|2), we demonstrate that some of these BPS multiplets, including all of the vacuum states of the matrix model plus certain infinite towers of excited states, have energies which are exactly protected non-perturbatively for any value of mu > 0. In the large N limit, these lead to exact quantum states of M-theory on the pp-wave. We also show explicitly that there are certain BPS multiplets which do receive energy corrections by combining with other BPS multiplets to form ordinary multiplets.