Here is a rather tedious proof:
Since $M$ is real, either the eigenvalues are all real, or there is one real and a pair of conjugate eigenvalues.
The key result here is that a real matrix has a real Jordan form, not quite upper triangular, but 'almost'. In the invertible $3 \times 3$ case, this means that there exists a real $V$ such that $J = V^{-1}MV$ has one of the following forms:
$J = \begin{bmatrix} \lambda_1 & M_{12} & 0 \\ 0 & \lambda_2 & M_{23} \\ 0 & 0 & \lambda_3\end{bmatrix} \ \ \ \ \ \ \ \ J = \begin{bmatrix} \lambda_1 & 0 & 0 \\ 0 & a & b \\ 0 & -b & a\end{bmatrix},$
where all the entries are real, $M_{12}, M_{23} \in \{0,1\}$, $\lambda_i \neq 0$ and $b \neq 0$.
In the second case, since all eigenvalues are distinct ($b \neq 0$), $S$ is diagonalizable over $\mathbb{C}$. We can take $S= V J V^{-1}$, $U= I$ and we are finished.
Now for the first case. Since this is the Jordan form, we have $(\lambda_1 \neq \lambda_2) \Rightarrow M_{12} = 0$, and similarly $(\lambda_2 \neq \lambda_3) \Rightarrow M_{23} = 0$.
Let $\Sigma = \mathbb{diag}(\lambda_1, \lambda_2, \lambda_3)$, and let $W = I + \alpha E_{12} + \beta E_{23}$, where $E_{12}$ is the matrix with zeros everywhere except a one in the $1,2$ position, and similarly for $E_{23}$. We want to determine constants $\alpha, \beta$ so that $J = \Sigma W = W \Sigma$. We have: $ \Sigma W = \Sigma + \alpha \lambda_1 E_{12} + \beta \lambda_2 E_{23}\\ W \Sigma = \Sigma + \alpha \lambda_2 E_{12} + \beta \lambda_3 E_{23}$
This shows that $\Sigma W = W \Sigma$ iff $\alpha( \lambda_1 - \lambda_2) = 0$ and $\beta( \lambda_2 - \lambda_3) = 0$. Furthermore, we want J$ = \Sigma W$, and this will be true iff $M_{12} = \alpha \lambda_1$, and $M_{23} = \beta \lambda_2$.
Let $\alpha = \frac{M_{12}}{\lambda_1}$ and $\beta = \frac{M_{23}}{\lambda_2}$, then it is easy to verify that all the conditions are satisfied. Then we can take $S = V \Sigma V^{-1}$, and $U = V W V^{-1}$, and we are finished.