Here's a solution using moment generating functions, as suggested by @SecretAgentMan, that also ties in with the very slick answer provided by @user158565. If you like, you can view this as an (overly) rigorous justification of the decomposition provided by @user158565.
Let $M \sim N(\theta, s^2)$ and $X|M \sim N(M,\sigma^2)$. We are asked to find the unconditional distribution of $X$. To this end, define $\varepsilon \equiv X - M$. We show that $\varepsilon \sim N(0, \sigma^2)$ by calculating its moment generating function (mgf). We have
\begin{align*}
\mathbb{E}\left[e^{t\varepsilon}\right] &= \mathbb{E}\left[\exp\left\{t(X-M)\right\}\right] = \mathbb{E}\left[\mathbb{E}\left(\left. e^{tX}e^{-tM}\right|M\right) \right]\\
&= \mathbb{E}\left[e^{-tM}\mathbb{E}\left(\left. e^{tX}\right|M\right) \right] = \mathbb{E}\left[ e^{-tM} \exp\left\{tM + \frac{1}{2}\sigma^2 t^2 \right\}\right]\\
&= \mathbb{E}\left[ \exp\left\{\frac{1}{2}\sigma^2 t^2 \right\}\right]
\end{align*}
using iterated expectations and the fact that $X|M$ is a normal random variable with mean $M$ and variance $\sigma^2$, so that its moment generating function is $\exp\left\{ tM + \frac{1}{2}\sigma^2 t^2 \right\}$.
We recognize $\mathbb{E}[e^{t\varepsilon}]$ as the mgf of a normal random variable, hence $\varepsilon \sim N(0,\sigma^2)$.
Next, we show that $M$ and $\varepsilon$ are independent by showing that their joint mgf equals the product of the respective marginal mgfs.
Again using iterated expectations and the mgf of $X|M$, we have
\begin{align*}
\mathbb{E}\left[ \exp\left\{ t_1 M + t_2 \varepsilon \right\} \right]
&= \mathbb{E}\left[ \exp\left\{ t_1 M + t_2(X -M) \right\} \right] = \mathbb{E}\left[ \exp\left\{(t_1 - t_2)M + t_2 X\right\} \right]\\
&= \mathbb{E}\left[ \exp\left\{(t_1 - t_2)M\right\} \mathbb{E}\left(\left. e^{t_2 X}\right|M \right) \right]\\
&= \mathbb{E}\left[ \exp\left\{(t_1 - t_2)M\right\} \exp\left\{ t_2 M + \frac{1}{2}\sigma^2 t_2^2 \right\} \right]\\
&= \mathbb{E}\left[ \exp\left\{ t_1 M + \frac{1}{2}\sigma^2 t_2^2 \right\} \right]\\
&= \mathbb{E}\left[e^{t_1 M}\right] \exp\left\{\frac{1}{2}\sigma^2 t_2^2 \right\} \\
&= \mathbb{E}\left[e^{t_1 M}\right] \mathbb{E}\left[ e^{t_2 \varepsilon} \right]
\end{align*}
as claimed. We have shown that $X = M + \varepsilon$ where $\varepsilon \sim N(0, \sigma^2)$ independently of $M \sim N(\theta, s^2)$. It follows that $X \sim N(\theta, s^2 + \sigma^2)$.