In this work, we exhaust all the spin-space symmetries, which fully characterize collinear, non-collinear, commensurate, and incommensurate spiral magnetism, and investigate enriched features of electronic bands that respect these symmetries. We achieve this by systematically classifying the so-called spin space groups (SSGs) - joint symmetry groups of spatial and spin operations that leave the magnetic structure unchanged. Generally speaking, they are accurate (approximate) symmetries in systems where spin-orbit coupling (SOC) is negligible (finite but weaker than the interested energy scale); but we also show that specific SSGs could remain valid even in the presence of a strong SOC. By representing the SSGs as O(N) representations, we - for the first time - obtain the complete classifications of 1421, 9542, and 56512 distinct SSGs for collinear (N=1), coplanar (N=2), and non-coplanar (N=3) magnetism, respectively. SSG not only fully characterizes the symmetry of spin d.o.f., but also gives rise to exotic electronic states, which, in general, form projective representations of magnetic space groups (MSGs). Surprisingly, electronic bands in SSGs exhibit features never seen in MSGs, such as nonsymmorphic SSG Brillouin zone (BZ), where SSG operations behave as glide or screw when act on momentum and unconventional spin-momentum locking, which is completely determined by SSG, independent of Hamiltonian details. To apply our theory, we identify the SSG for each of the 1604 published magnetic structures in the MAGNDATA database on the Bilbao Crystallographic Server. Material examples exhibiting aforementioned novel features are discussed with emphasis. We also investigate new types of SSG-protected topological electronic states that are unprecedented in MSGs.