Starting from the beginning (a very good place to start, after all), the state $\left| 0\right\rangle^{\otimes n}\left| -\right\rangle$ is input into $H^{\otimes n}\otimes I$ (here, called the 'Fourier sample'). This generates the state $$\left(\sum_{x=\{0,1\}^n}\frac{1}{2^{n/2}}|x\rangle\right)\left|-\right\rangle = \frac{1}{2^{n/2}}\left(\left|0\right\rangle + \left|1\right\rangle\right)^{\otimes n}\left|-\right\rangle.$$ Now, we apply the operation $U_f$ (in this case, the bit oracle) to give $$U_f\left(\sum_{x=\{0,1\}^n}\frac{1}{2^{n/2}}|x\rangle\right)\left|-\right\rangle = \sum_{x=\{0,1\}^n}\frac{1}{2^{n/2}}|x\rangle\left|-\oplus f\left(x\right)\right\rangle.$$
The first point to note is that $\oplus$ is the classical XOR operation. What this gives is actually the phase oracle, so that we get $$\left(\sum_{x=\{0,1\}^n}\frac{1}{2^{n/2}}\left(-1\right)^{f\left(x\right)}\left|x\right\rangle\right)\left|-\right\rangle.$$ This is because $U_f\left|x\right\rangle\left(\left|0\right\rangle - \left|1\right\rangle\right) = \left|x\right\rangle\left|f\left(x\right)\right\rangle - \left|x\right\rangle\left|1\oplus f\left(x\right)\right\rangle = \left(-1\right)^{f\left(x\right)}\left|x\right\rangle\left(\left|0\right\rangle - \left|1\right\rangle\right)$. This is the 'set up a superposition...' point - all this means is to perform the operations required to set the qubits in the above state, which is a superposition of all possible states (with phase factors, in this case). In this case, this is just Hadamard, followed by a phase oracle.
Now, $x$ is just a classical bit string: $x = \prod_ix_i$, so $$H\left|x_i\right\rangle = \frac{1}{\sqrt{2}}\left(\left|0\right\rangle + \left(-1\right)^{x_i}\left|1\right\rangle\right) = \frac{1}{\sqrt{2}}\sum_{y=\left\lbrace0, 1\right\rbrace}\left(-1\right)^{x_i.y}\left|y\right\rangle.$$
This gives the property $$H^{\otimes n}\left| x\right\rangle = \frac{1}{2^{n/2}}\sum_{y\in\left\lbrace0, 1\right\rbrace^n}\left(-1\right)^{x.y}\left|y\right\rangle.$$
This gives the final state as $$\frac{1}{2^n}\left(\sum_{x, y=\{0,1\}^n}\left(-1\right)^{f\left(x\right) \oplus x.y}\left|y\right\rangle\right)\left|-\right\rangle.$$
We know that $f\left(x\right) = u.x = x.u$, giving $\left(-1\right)^{f\left(x\right) \oplus x.y} = \left(-1\right)^{x.\left(u\oplus y\right)}$. Summing over the $x$ terms gives that $\sum_x\left(-1\right)^{x.\left(u\oplus y\right)} = 0,\, \forall\, u\oplus y \neq 0$. This means that we're left with the term for $u\oplus y = 0$, which means that $u=y$, giving the output as $\left|u\right\rangle\left|-\right\rangle$, which is measured to obtain $u$.
As for why we want to set up a superposition: This is where the power of quantum computing comes into play - In less mathematical terms, applying the Hadamard transformation is performing a rotation on the qubit states to get into the state $\left|+\right\rangle^{\otimes n}$. You then rotate each qubit in this superposition state using an operation equivalent to XOR (in this new basis), so that when performing the Hadamard transformation again, you're now just rotating back onto the state $\left|u\right\rangle$. Another way of looking at this is to consider it as a reflection or inversion that achieves the same result.
The point is that, using superposition, we can do this to all the qubits at the same time, instead of having to individually check each qubit as in the classical case.