Well if both functions can operate from a subset of R to a subset of R then I would suggest :
f(x) = - sqrt (x) and g(x) = x^2 then f(g(x) = -x strictly decreasing and g(f(x)) = x strictly increasing for x positive otherwise f is not defined.
But this sounds too simple...I would love to see an answer with complete mapping of R.
Just sitting on Michel's giant shoulders, try:
f(x) = - sign(x) . sqrt( |x| ) and g(x) = sign (x) . x^2 (with sign(x) = 1 if x > 0, -1 otherwise).
Both f and g are defined on all of R and f o g (x) = - sign (x) .|x| = - x, stricly decreasing and g o f (x) = sign (x) |x| = x, strictly increasing.
In fact this doesn't work by here $g\circ f=f \circ g$,
note that here: $f$ decreases, $g$ increases $\Rightarrow~g\circ f$ decreases
anyway solutions can't be continous,
(otherwise so are $g\circ f, \; f \circ g$ hence 1to1, so are $f,g$ hence strictly monotonous, and $g\circ f, \; f \circ g$, have same monotony).
We partition the real axis into a lot of intervals (for two functions the partion can be different.)
Let $h(x)=g\circ f(x)$, $k(x)=f\circ g(x)$.
First, we define an interval $A$ is low than another $B$ by $A$<$B$, if $\forall a\in A, b\in B$ such that $a$<$b$, like $(-1,2]$ is lower than $(2,4]$. If $h$ is increasing on $A$ and $B$, then we want the image of $A, B$ satisfying $h[A]$<$h[B]$; $k$ is decreasing on $A$ and $B$, then we want the image of $A, B$ satisfying $k[B]$<$k[A]$, which ensures the monotonicity (more) globally. With this idea, we can just arrange the map of partioned intervals.