Superposition in Quantum Mechanics First of all, let $V$ be a vector space over the field $\mathbb{F}$. It is possible then to show, by Zorn's Lemma that there is a basis for $V$. The main point is that although basis are quite convenient and their existance is something that helps a lot in Linear Algebra, an element $v\in V$ exists and has a meaning independent of any basis.
In truth, introducing a basis is just means to express each $v\in V$ uniquely as linear combination of a certain set of vectors. This produces a representation of $v$, but $v$ itself is independent of the representation, since given two basis we can work with either one of them and switch from one to another.
Now, in Quantum Mechanics if we let $\mathcal{H}$ be the Hilbert space describing the system and let $\left|\psi\right\rangle\in \mathcal{H}$ we can sometimes express $\left|\psi\right\rangle $ in a number of different basis in the same way I said above, since $\mathcal{H}$ is a topological vector space.
In other words we can express a state uniquely as superposition of certain states.
Now, my point is the following: I've already seem people talking about this saying that when we write $\left|\psi\right\rangle$ as the superposition
$$\left|\psi\right\rangle = \sum_{n=1}^{\infty}c_n \left|u_n\right\rangle$$
then a particle on the state $\left|\psi\right\rangle$ is simultaneously in all of the states $\left|u_n\right\rangle$. I think this is also the point of Schrödinger's cat.
Now, this is something that really bothers me. Because when we write such decomposition we are simply expressing $\left|\psi\right\rangle$ in a certain manner which can be convenient. The vector $\left|\psi\right\rangle$ is simply itself regardless of any bases. More than that, we can write it in any other basis we find convenient. In that setting, for me a basis is much more a convenient way to represent a vector than an essential part of what the vector is.
In that setting, what is behind this idea of superposition in Quantum Mechanics? Why people sometimes say that sort of thing, that the particle in the state $\left|\psi\right\rangle$ is simultaneously in all states $\left|u_n\right\rangle$? This makes any sense, considering my point?
 A: I had the same conceptual problems you are having when I was studying QM. Let me spray a bit of philosophy which allowed me to finally move on and concentrate on the mathematical stuff which actually matters :)
Quantum states are rays in the Hilbert space (or points in the projective Hilbert space, or etc.). All states have the same physical meaning: they all exist and none of them are special in any way.
The observable information is encoded in the Hilbert product structure defined on the space of states. In fact, the only reasonable question one could ask about a certain quantum system is of the following form:

What is the clash (module-squared of the inner product) $\left|\left<a|b\right>\right|^2$ of two given states $\left|a\right>$ and $\left|b\right>$ equal to?

But states are rather abstract beasts, and without a precise way in which we could identify states with actual experiences (or experimental setups, etc.) there won't be any meaning in any of such computations.
This is where observables come in, which in QM are encoded by self-adjoint operators. To each such operator we can assign a spectrum of eigenvalues and eigenstates.
I am going to use the Heisenberg picture here, so these operators change with time. Therefore, an operator at time $t _1$ is not the same as an operator corresponding to the same quantity at time $t _2 > t _1$.
We can then ask a physical question, which is:

I know for sure that my particle had coordinate $x = x_1$ at time $t = t _1$. In QM it means that I know for sure that the system is in such state $\left|a\right>$ that it is an eigenstate of the position operator at time $t _1$ with the corresponding eigenvalue:
  $$ \hat{x}(t _1) \left| a \right> = x _1 \left| a \right>. $$
  What possible outcomes could I experience when measuring the position of the particle at time $t _2$?

And QM has an elegant answer to this question. Since the system is in state $\left| a \right>$ which in general is not an eigenstate of the new position operator $x (t _2)$, I must expand it in terms of such eigenstates:
$$ \left| a \right> = \sum_{x_2} c_{x_2} \left| x _2 \right>. $$
If states are properly normalized (remember that actual states are rays rather than vectors in the Hilbert space), then clashes are given by the module-squared of the corresponding coefficients:
$$ \left| \left< a | x _2 \right> \right|^2 = \left| c _{x_2} \right|^2. $$
Some people are tempted to seek a more metaphysically pleasing meaning to this clashes. According to the Born rule (which has nothing to do with Jason Bourne btw), we could interpret this clash as a probability of experiencing state $\left| b \right>$ in some upcoming measurement given that we start from $\left| a \right>$.
To summarize: all states play the same role in QM, which is: they simply exist. But we are ultimately interested in ways to label states (or else how could we distinguish them and attach physical meaning?). This is done via eigenstates of self-adjoined operators.
But operators evolve with time. Therefore if we, for instance, have a state which is an eigenstate of some operator at time $t _1$, it is a superposition of (different) eigenstate of (different) operator corresponding to the same quantity but at time $t _2$.
Expansions of states over the basis are done when we are measuring some quantity. This basis is not at all arbitrary and consists of eigenstates of the self-adjoint operator corresponding to this quantity.
A: This gives a slightly more general formulation of Hindsight's answer. The most straightforward interpretation of superpositions in Quantum Mechanics is usually given in the context of orthogonal bases, which already involve more structure than the Hamel bases mentioned in the comments. For the purpose of keeping things simple, let us assume a countable basis $\{ | u_n \rangle \}_n $ as you did, and require in addition that it be orthonormal, $\langle u_n | u_m \rangle = \delta_{nm}$. Also let $\hat{ O }$ be some observable that has the $| u_n \rangle$-s as eigenstates, such that its eigenvalues are $\langle u_n | \hat{ O } | u_n \rangle$.  The decomposition of a normalized state $| \psi \rangle$ as a (unique) superposition 
$$
| \psi \rangle = \sum_{n} {c_n | u_n \rangle}
$$
with $c_n$ complex numbers, means that a measurement of $\hat{ O }$ on $| \psi \rangle$ will produce an output value $\langle u_n | \hat{ O } | u_n \rangle$ and an output state $| u_n \rangle$ with an amplitude $c_n$ and a probability $|c_n|^2$. On such grounds it is said in general that the coefficient $c_n$ is the amplitude of state $| u_n \rangle$ in state $| \psi \rangle $, and that there is a finite probability $|c_n|^2$ to measure state $| u_n \rangle$ in state $| \psi \rangle $. 
The concept is then extended to arbitrary amplitudes $\langle \phi | \psi \rangle$ for normalized states $| \phi \rangle $, since given any such $| \phi \rangle $ it is always possible to build an orthogonal basis that contains it. 
