The following interesting derivation is from Aigner's "A Course in Enumeration" (Springer, 2007).
Remember that if we have the following exponential generating functions:
$\begin{align}
\widehat{A}(z)
&= \sum_{n \ge 0} a_n \frac{z^n}{n!} \\
\widehat{B}(z)
&= \sum_{n \ge 0} b_n \frac{z^n}{n!}
\end{align}$
then also:
$\begin{align}
\widehat{A}(z) \cdot \widehat{B}(z)
&= \sum_{n \ge 0}
\left(
\sum_{0 \le k \le n} \frac{a_k}{k!} \frac{b_{n - k}}{(n - k)!}
\right) z^n \\
&= \sum_{n \ge 0}
\left(
\sum_{0 \le k \le n} \frac{n!}{k! (n - k)!} a_k b_{n - k}
\right) \frac{z^n}{n!} \\
&= \sum_{n \ge 0}
\left(
\sum_{0 \le k \le n} \binom{n}{k} a_k b_{n - k}
\right) \frac{z^n}{n!}
\end{align}$
Let's define:
$\begin{align}
S_m(n)
= \sum_{1 \le k \le n - 1} k^m
\end{align}$
We can define the exponential generating function:
$\begin{align}
\widehat{S}_n(z)
&= \sum_{m \ge 0} S_m(n) \frac{z^m}{m!} \\
&= \sum_{1 \le k \le n - 1} \sum_{m \ge 0} \frac{k^m z^m}{m!} \\
&= \sum_{1 \le k \le n - 1} \mathrm{e}^{k z} \\
&= \frac{\mathrm{e}^{n z} - 1}{\mathrm{e}^z - 1} \\
\end{align}$
This is almost the exponential generating function of the powers of $n$:
$\begin{align}
\widehat{P}_n(z)
&= \sum_{m \ge 0} n^m \frac{z^m}{m!} \\
&= \mathrm{e}^{n z}
\end{align}$
We can write:
$\begin{align}
(\widehat{P}_n(z) - 1) \widehat{B}(z)
= z \widehat{S}_n(z) \tag{1}
\end{align}$
where we have the exponential generating function of the Bernoulli numbers:
$\begin{align}
\widehat{B}(z)
&= \frac{z}{\mathrm{e}^z - 1} \\
&= \sum_{n \ge 0} B_n \frac{z^n}{n!}
\end{align}$
Comparing coefficients of $z^{m + 1}$ in (1):
$\begin{align}
\sum_{m \ge 1} z^m
\sum_{0 \le k \le m}
\binom{m}{k} \frac{(n z)^{m - k}}{(m - k)!} B_k
= \sum_{m \ge 0} S_m(n) \frac{z^{m + 1}}{m!}
\end{align}$
we get after simpĺifying:
$\begin{align}
S_m(n)
= \frac{1}{m + 1} \,
\sum_{0 \le k \le m} \binom{m + 1}{k} B_k n^{m + 1 - k}
\end{align}$
Note: The formula given is often associated with Faulhaber, but Faulhaber's formulas where quite different (and computationally more efficient). This formula is due to Bernoulli.