Solution:
Answer: $\left\{P(x)=x^{k} \mid k \in \mathbb{Z}^{+}\right\}$.

Note that if $P(\alpha)=0$, then by setting $x=\alpha-1$ in the given equation, we find $0=P\left(x^{3}+1\right)=P\left(\alpha^{3}-3 \alpha^{2}+3 \alpha\right)$. Because $P$ is nonconstant, it has at least one zero. Because $P$ has finite degree, there exist minimal and maximal roots of $P$. Writing $\alpha^{3}-3 \alpha^{2}+3 \alpha \geq \alpha \Longleftrightarrow \alpha(\alpha-1)(\alpha-2) \geq 0$, we see that the largest zero of $P$ cannot exceed $2$. Likewise, the smallest zero cannot be negative, so all of the zeroes of $P$ lie in $[0,2]$. Moreover, if $\alpha \notin\{0,1,2\}$ is a zero of $P$, then $\alpha' = \alpha^{3}-3 \alpha^{2}+3 \alpha$ is another zero of $P$ that lies strictly between $\alpha$ and $1$. Because $P$ has only finitely many zeroes, all of its zeroes must lie in $\{0,1,2\}$.

Now write $P(x)=k x^{p}(x-1)^{q}(x-2)^{r}$ for nonnegative integers $p, q$ and $r$ having a positive sum. The given equation becomes
$$\begin{aligned} & k^{2}(x+1)^{p} x^{q}(x-1)^{r}\left(x^{2}-x+1\right)^{p}\left(x^{2}-x\right)^{q}\left(x^{2}-x-1\right)^{r} = P(x+1) P\left(x^{2}-x+1\right) \\ & \quad = P\left(x^{3}+1\right) = k\left(x^{3}+1\right)^{p} x^{3q}\left(x^{3}-1\right)^{r} \end{aligned}$$
For the leading coefficients to agree, we require $k=k^{2}$. Because the leading coefficient is nonzero, $P$ must be monic. In $(*), r$ must be zero lest $P\left(x^{3}+1\right)=0$ have complex roots. Then $q$ must be zero as well. For, if $q$ is positive, then $P\left(x^{2}-x+1\right)=0$ has $1$ as a root while $P\left(x^{3}+1\right)$ does not. Finally, the remaining possibilities are $P(x)=x^{p}$ for $p$ an arbitrary positive integer. It is easily seen that these polynomials are satisfactory.