States in QM and in the algebraic approach In QM states are vectors in a Hilbert space $\mathscr{H}$. These are often denoted like $|\psi\rangle$.
On the other hand, in the algebraic approach, we have one $\ast$-algebra $\mathscr{A}$ and states are linear functionals $\omega : \mathscr{A}\to \mathbb{C}$ such that $\omega(a^\ast a)\in [0,\infty)$ and $\omega(1)=1$.
It is not at all clear how these two things are related.
For a first step, we have the GNS construction. The GNS construction is the following:

GNS Construction: Given a $\ast$-algebra $\mathscr{A}$ and a state $\omega : \mathscr{A}\to \mathbb{C}$ we can construct one Hilbert space $\mathscr{H}_\omega$, one $\ast$-representation $\pi_{\omega} : \mathscr{A}\to \mathscr{A}(\mathscr{H}_\omega)$ and one $\Omega \in \mathscr{H}$ such that $\pi_{\omega}(\mathscr{A})\Omega$ is dense and $$\omega(a)=\langle \Omega ,\pi_\omega(a)\Omega\rangle.$$

Now we have some interesting things:


*

*Every algebraic state $\omega$ gives rise to a whole Hilbert space on which $\omega$ becomes the distinguished $\Omega$ and it produces one mean value on the usual QM sense.

*The other unit vectors on the Hilbert space give rise to algebraic states. Actually, if $\Phi\in \mathscr{H}$ we have that
$$\omega_\Phi(a)=\langle \Phi, \pi_{\omega}(a)\Phi\rangle$$
is one algebraic state. It is obviously a linear functional and certainly satisfies $\omega_{\Phi}(1)=1$ and $$\omega_{\Phi}(a^\ast a)=\langle \Phi,\pi_{\omega}(a^\ast a)\Phi\rangle=\langle \Phi,\pi_{\omega}(a^\ast)\pi_{\omega}(a)\Phi\rangle=\langle \Phi,\pi_{\omega}(a)^\ast \pi_\omega(a)\Phi\rangle=\langle \pi_\omega(a)\Phi,\pi_{\omega}( a)\Phi\rangle=|\Phi|^2\in [0,+\infty)$$

*On the other hand it doesn't seem that every algebraic state gives rise to one usual state in $\mathscr{H}_\omega$. In truth, because of the Riesz representation theorem it would suffice that to every algebraic state $\phi$ there was one algebraic state $\tilde{\Phi}$ on $\mathscr{A}(\mathscr{H}_\omega)$. This in turn requires that $\tilde{\Phi}(\pi_{\omega}(a))=\phi(a)$ thus for this to be true we would need $\pi_\omega$ to be invertible. In other words, the representation must be faithful.
These points show that although related to the usual state vectors from QM, the algebraic states aren't equivalent to them. In fact, it seems we have more algebraic states than state vectors.
Furthermore, GNS allows us to indeed represent each state as a state vector, but on different Hilbert spaces. The point (2) I made then guarantee that each such state vector can be identified with one algebraic states, but there are other apart from it which do not belong on this Hilbert space. Even, though, if we pick one of those states in (2) and perform the GNS construction with them it seems we get an entirely different Hibert space.
It seems that the role of algebraic states is to generate a representation only and this is quite strange, considering the usual QM point of view on states.
So what is the correct way to understand algebraic states? How they relate to the usual notion of states from QM? To work with them in practice do we always need to use the GNS construction? 
How do we deal with the fact that it appears that there are more algebraic states than QM vector states, in the sense that when we perform the GNS construction some algebraic states appear to be "left out"?
 A: The essential mistake in your reasoning is that you contrast the wrong notions of "state" - the algebraic states are not only supposed to be pure vector states, i.e. represented by vectors in the "natural" Hilbert space of the system, but they also include all mixed states, i.e. density matrices. Of course there are "more" (in the sense of dimensionality of the vector space these states form) mixed states than pure states.
There is an abstract condition for an algebraic state to be "pure", which is to be an extremal point of the space of algebraic states. "Extremal" is a well-defined condition because the set of algebraic states is convex as a subset of the dual of the $C*$-algebra, which is a Banach space because the $C*$-algebra itself is one. So you just need to GNS-construct Hilbert space where the pure states are represented by vectors, you get the mixed states as the density matrices on that space "for free".
A: The algebraic formulation is more general and takes into account many subtleties that arise in QFT and that are hidden in quantum mechanics.
In fact, in quantum mechanics the Stone-von Neumann theorem tells us that the irreducible representation of the algebra of quantum observables (more precisely, of the algebra of canonical commutation relations) is essentially unique (i.e. it is unique up to unitary transformations). So the only relevant representation is the usual one (called Schrödinger representation), and the physically relevant states are the ones that are normal with respect to such representation (i.e. that can be written as density matrices on the corresponding Hilbert space $L^2(\mathbb{R}^d)$).
In quantum field theories, on the other hand, there are infinitely many inequivalent irreducible representations of the canonical (anti)commutation relations. Therefore, there are indeed states that can be represented as density matrices (or vectors) in one representation, but not in another (it is said that they are not normal with respect to the latter).
In addition, the so-called Haag's theorem explains that inequivalent representations, or more precisely disjoint states (states that are not normal w.r.t. the GNS irrepresentation of each other), play a very important role in QFT. In fact, given a group $G$ acting on the C*-algebra of observables, and two $G$-invariant states $\omega_1,\omega_2$ (with an additional technical condition that is not important here), then either $\omega_1=\omega_2$, or $\omega_1$ and $\omega_2$ are disjoint. In a relativistic theory, the ground state (or vacuum) is invariant w.r.t. the restricted Poincaré group. In addition, it is easy to see that in general the vacua of a free and an interacting theory must be different (and both invariant). Therefore, by Haag's theorem they are disjoint, and so they cannot both be represented as density matrices in a single representation.
This is just one example of why non-normal states (w.r.t. the free or Fock irrepresentation) are very important in QFT, and of why the algebraic description of quantum theories is so often used for relativistic quantum mechanics.
