Is $f(x)$ necessarily a polynomial if $f(f(x))$ is?

The answer is negative. Let $f$ be any involution on $\mathbb{R}$ i.e. any function whose graph is symmetric with respect to the line $y=x$. Then $g(x)=f(f(x)) = x$ is a polynomial, but not all involutions $f$ are polynomials.

It is possible for $f(x)$ to not be a polynomial. For instance, let $\alpha:\mathbb{R}\to\mathbb{R}$ be a diffeomorphism, and define $f_\alpha=\alpha^{-1}\circ h\circ\alpha$ where $h(x)=-x$. These functions all satisfy $f_\alpha(f_\alpha(x))=x$, but they cannot be polynomials for every possible choice of $\alpha$. Indeed, notice that if $\alpha'=\alpha$ on both an interval $(a,b)$ and on the interval $\alpha^{-1}(h(\alpha(a)),h(\alpha(b)))$, then $f_\alpha=f_{\alpha'}$ on $(a,b)$. You can easily have two diffeomorphisms $\alpha$ and $\alpha'$ which agree in this way on two intervals, but which disagree elsewhere such that $f_\alpha$ and $f_{\alpha'}$ are not the same everywhere (since using bump functions, you can freely vary a diffeomorphism locally). It follows that $f_\alpha$ and $f_{\alpha'}$ cannot both be polynomials, since a polynomial is determined by its values on an interval.

To be more explicit, you could take $\alpha(x)=x$ and let $\alpha'(x)=x+\varphi(x)$ where $\varphi$ is a nonzero smooth function on $\mathbb{R}$ with compact support such that the derivative of $\varphi$ is always strictly between $-1$ and $1$. Then $f_\alpha(x)=-x$ for all $x$, and $f_{\alpha'}(x)=-x$ if $x$ and $-x$ are both not in the support of $\varphi$. But if $x$ is such that $\varphi(x)\neq 0$ then $f_{\alpha'}(x)=-x-\varphi(x)\neq -x$. Thus $f_{\alpha'}$ is not a polynomial.