What do these labels for molecular electronic states mean?
As stated in this answer, these are irrep (irreducible representation) labels for molecular symmetry point groups. In the context of chemistry, point groups are usually introduced when learning about structural symmetry (atoms and bonds). This is a broad topic with many technical points, too many for a single answer, so I won't cover the basics but hopefully the few things needed to make the connection between what you read in a book and what's present in this paper.

The key is recognizing that the structural symmetry of molecules leads to symmetry in their molecular orbitals. Take the water molecule as an example. Water's molecular structure can be described at best by the $C_{2v}$ point group, so we say it has $C_{2v}$ symmetry. Composing its molecular orbitals from atomic orbitals is actually an exercise in symmetry, as only atomic orbitals of identical symmetry may combine. Here is the LCAO-MO diagram for water, with the oxygen 1s orbital left out due to its extremely low energy; it won't mix with the hydrogen AOs.



Here is the character table for the $C_{2v}$ point group.



AOs of identical symmetry (they transform identically for any given symmetry operation) are shown in the same color. A few things are worth pointing out:


s orbitals are perfectly symmetric (a sphere), so they will always transform as the totally symmetric irrep of a molecular point group. In $C_{2v}$, that's $A_1$. Once you learn what the operations $E$, $C_{2}$, $\sigma_{v}(xz)$, and $\sigma_{v}(yz)$ do, you can convince yourself that the $\sigma$ combination of $\ce{H2}$ AOs is also completely symmetric under those operations, so it also belongs to the $A_1$ irrep. The p orbitals are figured out from the 3rd column, d from the 4th.
The 2s and $\sigma$ AOs combine to give the $3a_1$ MO. The "3" is because it's the 3rd such MO with $a_1$ symmetry. The symmetry label is in lowercase because it for a 1-electron state. Symmetry labels are in uppercase for many-electron states, such as the total wavefunction, as you see in the linked paper. This is a matter of convention, nothing more.


Neutral water is a closed-shell molecule; there aren't any unpaired electrons, so it has singlet spin multiplicity. How do you determine the symmetry of the total wavefunction? A Slater determinant can help, or even just the Hartree product part of it. Take a fictitious system with 4 electrons in 2 orbitals. The Hartree product will look something like

$$
\Psi_{\text{Hartree}} = [\phi_{1}(1)\alpha(1)][\phi_{1}(2)\beta(2)][\phi_{2}(3)\alpha(3)][\phi_{2}(4)\beta(4)]
$$



This is a product wavefunction that might be made from an electron configuration such as $1s^{2}2s^{2}$, $1s^{2}2p_{x}^{2}$, $4p_{x}^{2}4p_{z}^{2}$. Each of these MOs has a certain symmetry; the total symmetry is given by the product of the individual symmetries. For this step one needs the point group product table (again for $C_{2v}$):

$$
\begin{array}{|l|l|l|l|l|}
\hline
            &amp; \mathbf{A_1} &amp; \mathbf{A_2} &amp; \mathbf{B_1} &amp; \mathbf{B_2} \\ \hline
\mathbf{A_1} &amp; A_1          &amp; A_2          &amp; B_1          &amp; B_2          \\ \hline
\mathbf{A_2} &amp; A_2          &amp; A_1          &amp; B_2          &amp; A_1          \\ \hline
\mathbf{B_1} &amp; B_1          &amp; B_2          &amp; A_1          &amp; A_2          \\ \hline
\mathbf{B_2} &amp; B_2          &amp; B_1          &amp; A_2          &amp; A_1          \\ \hline
\end{array}
$$

If the electron configuration of the system is indeed $4p_{x}^{2}4p_{z}^{2}$, this results in a total wavefunction symmetry of

$$
B_{1} \times B_{1} \times A_{1} \times A_{1} = A_{1}
$$

The spin components don't contribute, only the spatial components. Note that in any product table, the product of any irrep with itself is always the totally symmetric representation in that group, hence the diagonal being all $A_{1}$. Product tables are also symmetric, since irreps are commutative under multiplication. Since this is a singlet, the ground-state wavefunction can be specified as $^{1}\!A_{1}$. For a closed-shell system (RHF), due to the pairs of electrons always leading to $A_{1}$ symmetry, it will always have a total state symmetry of $^{1}\!A_{1}$. If you have an open-shell system of any kind in a ground or excited state, with either an even or odd number of electrons, the total wavefunction symmetry will be determined by electrons in those orbitals alone, since the product between fully-occupied orbitals will always be of $A_{1}$. In the simplest case of one unpaired electron, the total symmetry of the ground state will be the symmetry of the SOMO.

Now, on to the paper. The most important part for our understanding of the state label assignments is Table 3:



All the systems considered have either $C_{2v}$ or $C_{s}$ symmetry. Note how going from a point group of higher symmetry ($C_{2v}$, 4 irreps) to one of lower symmetry ($C_{s}$, 2 irreps) leads to states collapsing into fewer irreps due to fewer symmetry operations that can distinguish them. For the plots (here the last row of Figure 6),



there is the isosurface of the molecular orbital (really a natural orbital), the orbital number and symmetry, and the natural orbital occupation number (NOON) for that NO in that state.

There are a number of good Dover publications (1, 2, 3) for learning about group theory in chemistry and spectroscopy that are highly recommended, since the primary peer-reviewed literature isn't usually a good resource for learning this. An excellent resource for character tables is WebQC.