Why mass, charge and spin are good labels for elementary particles? Why mass and charge are good quantities to labels elementary particles? 
[I know that what qualifies to be a good label must be a quantity that is invariant under some kind of transformation, but why this criteria? I just do not understand what good does using such invariant quantities buy us]
 A: Well one could label them as they were being found, as was the case when the first cosmic ray and bubble chamber studies of charged  tracks in cloud chambers and emulsions and later electronic detectors were detected. That is what happened at the beginning, they took the greek alphabet and named alpha particles and beta particles and gamma particles  and later we get delta( a nucleon resonance) and eta and pi and rho and psi and xi and ...
Is that a better way of labeling them?
Noticing that there exist invariant quantities in the relativistic and quantum mechanical frameworks  allowed to organize these over a hundred particles into a structure, analogous  to a crystal structure in solids, called the standard model.  This, in addition to charge mass and spin organized the particles into group structures that appear naturally  or imply naturally  theories needed to study elementary particle interactions, and thus extend our knowledge of nature.
To answer the comment:

Is this idea, namely looking for invariants to lable states or particles, natural? It sounds deep to me, I mean is it really an idea that anybody could have "naturally" thought of?

Invariants are used for labeling in all human labeling systems and the answer is self evident in the word. Fingerprints, retinas come easily to mind, DNA of course. Why are they used? Because they do not change through the transformations that a person may undergo. It is a natural organizing principle to look for invariants in landscapes, in biological systems, in evolution, etc. In a similar way, "invariant" for a particle means a quantity that is immutable to transformations that it may undergo and they serve to pin its identity. For particle the transformations are mathematically defined.
Particularly for physics, if one studies classical physics, invariants of motion were very much to the front, so yes, it is natural to look for invariants and utilize them as I illustrated above.
A: The states of a system are in a big Hilbert space $\mathcal{H}$. The states seen by different inertial observers are related by a representation $U(g)$ of the Poincare group. So, if Alice prepares a state $|\psi\rangle$, then Bob sees this as state $|\psi'\rangle=U(g)|\psi\rangle$; a general state $|\psi\rangle$ will be sent to some state $|\psi'\rangle$ with no simple relation to $|\psi\rangle$. However, by using the structure of the group, the big Hilbert space $\mathcal{H}$ decomposes into a direct sum of smaller irreducible subspaces as,
$$ \mathcal{H}=\oplus \mathcal{L}_{au}$$
where the subspaces are the $\mathcal{L}_{au}$ and $a$ labels the inequivalent subspaces and  $u$ labels the copies of subspace $a$. The states which span the subspace $\mathcal{L}_{au}$ are $|a,i,u\rangle$ for $i=1,\ldots,n_{a}$. Now, if Alice prepares a system in state $|a,i,u\rangle$, then Bob sees this system in state $U(g)|a,i,u\rangle \in \mathcal{L}_{au}$; Bob's state remains  in the small subspace $\mathcal{L}_{au}$ because $U(g)|a,i,u\rangle$ is just a linear combination  of the  $|a,j,u\rangle$ for different values of $j$. So, if a state belongs to an irreducible  subspace $\mathcal{L}_{au}$, it is the most elementary kind of system that can exist. Such a system is called a "particle" because the states in the subspace  $\mathcal{L}_{au}$ constitute the smallest set of states which Alice and Bob and all other inertial observers can agree to call different views of the same thing. (This argument applies to any space  which carries a group representation and not just the states seen by inertial observers connected by the Poincare group; this notation reflects the general case.)
What we call the "properties" of the particle or an elementary system are just the labels $a$ of the inequivalent irreducible subspaces $\mathcal{L}_{au}$. If one finds the irreducible subspaces that carry a unitary representation of the Poincare group, the states are $|M,s;p,m\rangle$ where $M$ is mass, $s$ is spin, $p$ is 4-momentum and $m=s,s-1,\ldots,-s$ is the z-component of spin. The pair $(M,s)$ form the label  $a$  of the inequivalent irreducible subspaces; they are the "properties" of the particle, the pair  $(p,m)$ form the label $i$  that selects the states spanning  the subspace $\mathcal{L}_{au}$ and there are no copies  $u$ in this case. The momentum labels $p$ are coords of points on an orbit $p^{2}=M^{2}$ and this is the clue that the label $M$ is what we call mass.
