Solution:
Changing $\theta$ to $\theta - \pi / 2$, we see that
$$P(\sin \theta + \cos \theta) = P(\sin \theta - \cos \theta)$$
This shows that $P(x) = P(-x)$ for all $x \in [-\sqrt{2}, \sqrt{2}]$ and as $P$ is a polynomial, in fact,
$$P(x) = P(-x)$$
for all $x \in \mathbb{R}$. Hence $P(x)$ is an even polynomial; $P(x) = Q(x^{2})$ for some polynomial $Q(x)$. This gives
$$Q(1 + \sin(2\theta)) = P(\cos \theta + \sin \theta) = P(\cos \theta - \sin \theta) = Q(1 - \sin(2\theta))$$
Taking $t = \sin(2\theta)$, we see that $Q(1 + t) = Q(1 - t)$. Hence $Q(0) = Q(2)$.

Consider $Q(t) - Q(0)$. This vanishes both at $t = 0$ and $t = 2$. Hence $t(2 - t)$ is a factor of $Q(t) - Q(0)$. We obtain
$$Q(t) - Q(0) = t(2 - t) h(t)$$
for some polynomial $h(t)$. Using $Q(1 + t) = Q(1 - t)$, it follows that $h(1 + t) = h(1 - t)$. Hence by induction we get
$$Q(t) = \sum_{k=0}^{n} b_{k} t^{k} (2 - t)^{k}$$
Hence
$$P(x) = Q(x^{2}) = \sum_{k=0}^{n} b_{k} (x^{2}(2 - x^{2}))^{k} = \sum_{k=0}^{n} b_{k} (1 - (1 - x^{2})^{2})^{k}$$
Using binomial theorem, we can write this as
$$P(x) = \sum_{k=0}^{n} a_{k} (1 - x^{2})^{2k}$$
for some coefficients $a_{k}$, $0 \leq k \leq n$.