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}$.