I remember one of my professors mentioning this fact during a class I took a while back, but when I searched my notes (and my textbook) I couldn't find any mention of it, let alone the proof.
My best guess is that it has something to do with Galois theory, since it's enough to prove that the characters are rational – maybe we have to find some way to have the symmetric group act on the Galois group of a representation or something. It would be nice if an idea along these lines worked, because then we could probably generalize to draw conclusions about the field generated by the characters of any group. Is this the case?
Best Answer
If $g$ is an element of order $m$ in a group $G$, and $V$ a complex representation of $G$, then $\chi_V(g)$ lies in $F=\mathbb{Q}(\zeta_m)$. Since the Galois group of $F/\mathbb{Q}$ is $(\mathbb{Z}/m)^\times$, for any $k$ relatively prime to $m$ the elements $\chi_V(g)$ and $\chi_V(g^k)$ differ by the action of the appropriate element of the Galois group.
If $G$ is a symmetric group and $g$ an element as above, then $g$ and $g^k$ are conjugate: they have the same cycle decomposition. So $\chi_V(g)=\chi_V(g^k)$ whenever $(k,m)=1$, and thus $\chi_V(g)\in \mathbb{Q}$.
Now, because $\chi_V(g)$ is an algebraic integer (true for every finite group, every complex character) and a rational number, it is a rational integer, that is, an integer: $\chi_V(g)\in\mathbb{Z}$.