I am reading this paper by Simon. This is one of the earliest quantum algorithm papers. In the paper he presents a routine starting at the end of page six. The first step runs a Fourier transformation on a string of $n$ zeroes producing $2^{-\frac{n}{2}} \sum_x |x\rangle$. I understand that $x \in \{0, 1\}^n$.
Does the summation mean sum over all possible permutation of $\{0, 1\}^n$? If so, still I don't see how this sum is equal to $|0^n\rangle$.
At the same time, I don't see where the $y$ comes from in step 3.
The Fourier transform $F$ is defined (here) as $$ F|x\rangle = 2^{-n/2}\sum_{y\in \{0,1\}^n} (-1)^{x\cdot y}|y\rangle. $$ So the answer to you last question is that $y$ is a dummy variable indexing the sum. Not that if we apply $F$ to the state $|0^n\rangle$, we get $$ F|0^n\rangle= 2^{-n/2}\sum_{x\in \{0,1\}^n} (-1)^{0^n\cdot x}|x\rangle = 2^{-n/2}\sum_{x\in \{0,1\}^n}|x\rangle. $$ This is step 1. I haven't gone through the details but I think step 2 is to introduce $n$ more qubits (WLOG in the state $0^n\rangle$) and perform a sequence of gates $U_f$ which maps $$ U_f |x\rangle \otimes |0^n\rangle = |x\rangle\otimes|f(x)\rangle =:|x,f(x)\rangle. $$ Now step 3 is just to apply $F$ again on the first $n$ qubits: \begin{align} F\otimes \mathbb I \left(2^{-n/2}\sum_{x\in \{0,1\}^n}|x,f(x)\rangle\right) &= 2^{-n/2}\sum_{x\in \{0,1\}^n}F|x\rangle\otimes|f(x)\rangle,\\ &= 2^{-n} \sum_{y\in \{0,1\}^n}\sum_{x\in \{0,1\}^n}(-1)^{x\cdot y}|y\rangle\otimes|f(x)\rangle. \end{align}