The answer is rather involved, but here’s the general idea: we can define an inner product on the space of symmetric functions $\Lambda^n$ in such a way that the Schur functions form an orthonormal basis:
$$\langle s_{\lambda},s_{\mu}\rangle=\begin{cases} 1 & \text{if }\lambda=\mu \\ 0 &\text{otherwise}\end{cases}$$ This is known as the Hall inner product, and is well-defined for all symmetric functions since the Schur functions form a basis.

Furthermore, the Schur functions are also known to be a basis for the $\mathbb{Z}$-module consisting only of the symmetric functions having integer coefficients. And they are the unique such orthonormal basis up to sign and order, since any transition matrix to another basis must be integral and orthogonal with respect to the Hall inner product. But any integral orthogonal matrix must be a signed permutation matrix (this is another cute problem!)

It can be shown in a similar fashion that the irreducible characters of $S_n$ also are the unique (up to sign and order) integral basis of the space of virtual characters, that is, the integer linear combinations of characters.

Finally, the Frobenius map is known to be an isometry, in which the standard inner product on characters given by $\langle \chi,\psi\rangle=\frac{1}{n!}\sum_{\pi\in S_n} \chi(\pi)\psi(\pi)$ is used to define the norm on virtual characters. This implies that the two orthonormal bases – the irreducible characters and the Schur functions – must be sent to each other by the Frobenius map.

Let’s look at what this implies. By the original definition of the Frobenius map, we have
$$F(\chi^{\lambda})=s_\lambda=\sum_{\mu}\frac{1}{z_\lambda}\chi^{\lambda}(\mu)p_\mu.$$ So, to find a combinatorial rule for the entries $\chi^{\lambda}(\mu)$ of the character table, one only needs to find a combinatorial rule for expressing the Schur basis in terms of the power sum basis! And the Murnaghan-Nakayama rule comes about as a result.

This was just a general sketch of the proof; for full details see Enumerative Combinatorics, Vol. 2 by Richard Stanley, or The Symmetric Group, by Bruce Sagan. In any case, the use of the Frobenius map is the key step, turning an otherwise difficult problem in representation theory into a purely combinatorial problem about symmetric functions.