Why are the characters of the symmetric group integer-valued? 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?
 A: 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}$.
A: The characters of any representation are always algebraic integers since they are sums of roots of unity.  Over the symmetric group, every representation is defined over $\mathbb{Q}$, and the integers are integrally closed.  Indeed, the irreducibles can be constructed by using Young projectors that use only rational numbers.
(Another way to see that every representation is defined over $\mathbb{Q}$ is that all conjugacy classes are rational; this is what Charles indicated in his answer.)
A: I just want to emphasize that this question points at the rationality theory of representations and characters that is exposed so beautifully in Chapters 12 and 13 of Serre's book Linear Representations of Finite Groups.  
In particular, one has the following facts.
[Section 13.1, Corollary 1]: The following are equivalent:
(i) Every character of $G$ is $\mathbb{Q}$-valued.
(ii) Every character of $G$ is $\mathbb{Z}$-valued.
(iii) Every conjugacy class of $G$ is rational: for every $g \in G$ and positive integer 
$k$ prime to the order of $g$, $g^k$ is conjugate to $g$.  
As noted above, since raising an element of the symmetric group $S_n$ to a power prime to its order does not change the cycle decomposition, condition (iii) holds and the implication (iii) $\implies$ (ii) answers the question.  [The proof is the basic Galois-theoretic argument given in some other answers.  The implication (ii) $\implies$ (iii) is deeper in that it uses the irreduciblity of the cyclotomic polynomials.]  
Some others have said that the shortest or simplest proof arises from knowing that all of the irreducible representations of $S_n$ can be explicitly constructed and therefore seen to be realizable over $\mathbb{Q}$.  I respectfully disagree.  This is a nontrivial theorem of Young which Serre refers to but does not prove in his book (Example 1, p. 103).  
Moreover, Serre explains that the condition of rationality of characters is in general weaker than rationality of representations: there are obstructions here in the Brauer group of $\mathbb{Q}$!  Namely, by Maschke's Theorem the group ring $\mathbb{Q}[G]$ is semisimple, say a product of simple $\mathbb{Q}$-algebras $A_i$ which are in bijective 
correspondence with the irreducible $\mathbb{Q}$-representations $V_i$.  By Schur's Lemma, 
$D_i = End_G(V_i)$ is a division algebra, and one has $A_i \cong M_{n_i}(D_i)$.  Then:
[Section 12.2, Corollary]: The following are equivalent:
(i) Each $D_i$ is commutative.
(ii) Every $\mathbb{C}$-representation of $G$ is rational over the abelian number field generated by its character values.
Thus just knowing that the character table is $\mathbb{Z}$-valued is not enough.  The standard example [Exercise 12.3] is the quaternion group $G = $ {$\pm 1, \pm i, \pm j, \pm k$} for which
$\mathbb{Q}[G] \cong \mathbb{Q}^4 \oplus \mathbb{H}$, 
where $\mathbb{H}$ is a division quaternion algebra over $\mathbb{Q}$, ramified at $2$ and $\infty$.  It corresponds to an irreducible $2$-dimensional $\mathbb{C}$-representation with rational character but which cannot be realized over $\mathbb{Q}$.  
A: Galois theory is probably the best and simplest explanation, and the most amenable to generalization for other groups (and more general number fields). This is already well-expounded in earlier answers. I just want to point out that it was already known to Frobenius that all irreducible characters of $S_{n}$ are $\mathbb{Z}$-combinations of permutation characters ( ie characters induced from trivial characters of subgroups). More precise information became available later (Young tableaux, etc, as mentioned in other answers), but what Frobenius knew already covered the question.
A: The quickest answer is because all of the irreducible representations of the symmetric group can be constructed over the field of rational numbers. See the wikipedia article on Young symmetrizers for example http://en.wikipedia.org/wiki/Young_symmetrizer
More generally, one can say that representations of any finite Weyl group can be constructed over the rational numbers. This is explained in one of Springer's papers: http://www.ams.org/mathscinet-getitem?mr=491988
Another reason is that one write down an explicit combinatorial formula for the values of these characters. This is the Murnaghan-Nakayama rule and can be found in many sources. One such source is Stanley's Enumerative Combinatorics volume 2, Section 7.17, and Section 7.18 for its connection to the symmetric group.
A: One way to prove that you get integers is to prove that the corresponding simple modules are defined over $\mathbb Z$ (this is of course much stronger than their having characters with values in $\mathbb Z$), and this is what you get by constructing them 'combinatorially'.  This is done in G. D. James's book on the representation theory of symmetric groups, for example. There he even constructs actual matrices giving the action of elements of $S_n$ on the simple modules---the so called Young orthogonal form.
A: Based off cursory googling (I am by no means even a novice at this material, more like a baby), the assertion that every irreducible representation of $S_n$ is defined over $\mathbb{Q}$ seems to follow from Springer theory, but I think we would like a more elementary proof. I think Schur-Weyl duality and the Borel-Bott-Weil theorem should also work?
Anyways, the point being that the "reason" why $S_n$ has irreducible representations defined over $\mathbb{Q}$ is because it is associated to an algebraic group over $\mathbb{Q}$, and so basically any ways of dealing with irreducible representations of Weyl groups will show this. That being said, there is an extra detail in Springer theory out of type A that makes me hesitant to say this works for all Weyl groups... but I think it does? Could anyone lend their insight?
