Assuming that $g(x) > x$ rather than $g(x) \geq x$ for all $x$, and also that $g$ is strictly increasing (no critical points), one can obtain a solution $f$ to $g = f \circ f$ which piecewise has roughly similar properties to $g$, in particular $f$ will also be strictly increasing with $f(x)>x$. Things look to be more interesting if one relaxes these hypotheses.

Here's the construction. Firstly, define $x_n$ iteratively for $n=0,1,\dots$ by $x_0 := 0$, $x_{n+1} := g(x_n)$, then the $x_n$ will be increasing to infinity (they cannot accumulate at any finite point $x_*$ as one would then have $g(x_*)=x_*$).

Now also define $x_n$ for half-integers $n=1/2,3/2,\dots$ by picking $x_{1/2}$ arbitrarily between $x_0,x_1$ and then setting $x_{n+1} := g(x_n)$ for $n=1/2,3/2,\dots$. The $x_n$ for half-integer $n$ interlace between the $x_n$ for integer $n$, so the $x_n$ still increase to infinity as $n$ ranges over the combined index set $0,1/2,1,3/2,\dots$.

For any $n$ in this combined index set, the function $g$ is a continuous increasing map from $[x_n,x_{n+1/2}]$ to $[x_{n+1},x_{n+3/2}]$ that maps endpoints to endpoints, and must therefore be a bijection (by the intermediate value theorem) and thus a homeomorphism (as both domain and range are compact Hausdorff). Call $g_n: [x_n,x_{n+1/2}] \to [x_{n+1}, x_{n+3/2}]$ the restriction of $g$ to these intervals. To finish the job it will suffice to find increasing homeomorphisms $f_n:[x_n,x_{n+1/2}] \to [x_{n+1/2},x_{n+1}]$ mapping endpoints to endpoints such that $g_n = f_{n+1/2} \circ f_n$ for all $n=0,1/2,\dots$. This has "decoupled" the two factors of $f$ in the original equation $g = f \circ f$ and it is now easy to describe the general solution to this by writing the equation as $f_{n+1/2} = g_n \circ f_n^{-1}$ and solving recursively. More explicitly: pick an arbitrary increasing homeomorphism $f_0: [x_0,x_{1/2}] \to [x_{1/2},x_1]$ mapping endpoints to endpoints, and set $f_n := g^n \circ f_0 \circ g^{-n}$ for integer $n$ and $f_n := g^{n+1/2} \circ f_0^{-1} \circ g^{1/2-n}$ for half-integer $n$.

The function $f$ produced here by gluing together the $f_n$ will be continuous and strictly increasing and obey the required equation $g = f \circ f$ (in fact this is the general solution to this equation with the stated properties, bearing in mind that $x_{1/2}$ is also arbitrary between $x_0$ and $x_1$). If $g$ has no critical points then the $f_n$ will be diffeomorphisms and thence the $f_n$ will also. So $f$ will be smooth except possibly at the transition points $x_n$. Actually one can fix things up to be smooth at the endpoints also: if one extends $f_0$ a bit past $x_{1/2}$ to an extension $\tilde f_0$ that stays smooth near $x_{1/2}$ without critical points, and then modifies $f_0(x)$ smoothly near $x_0$ to equal $\tilde f_0^{-1}(g(x))$ for $x$ sufficiently close to $x_0$, then one can check that $f$ is now smooth everywhere. The situation becomes more interestingly complicated when $g$ has critical points $g'(x)=0$ or fixed points $g(x)=x$, but I haven't looked into this carefully (presumably the analysis of the analytic case in other answers will indicate what the behaviour should be there).

2more comments