If $f(f(x))$ is a linear function, must $f(x)$ be linear? I'm thinking of $f$ as a function either from the reals to the reals or from the naturals to the naturals. 
Edit: Okay, what if $f$ is from the naturals to the naturals? 
 A: If you want one from the naturals to the naturals, take $f(x)$ to be the function $f(1)=2,f(2)=1$, and $f(n)=n$ for $n\geq 3.$
A: Another family of examples for $\mathbb N$: 
Let $p$ be prime, $q$ coprime to $p$.  $f(n) = p n$ if the $p$-adic order of $n$ is even (i.e. $n = p^e m$ where $e$ is even and $m$ is coprime to $p$), otherwise $f(n) = q n/p$.  Then $f(f(x)) = q x$.  
A: No. For example,$$
f(x) = \begin{cases}
\displaystyle \frac{1}{x}; & x \neq 0\\
0; & x = 0
\end{cases}.
$$
A: As for $\Bbb N$, let $f(n)=n+1$ for odd and $=n-1$ for even $n$. One can twist this to fancier constructions by fancier partitions of $\Bbb N$.
A: This doesn't directly answer the question, but if $f$ is continuous from $\mathbb{R}\to\mathbb{R}$, it still can be nonlinear. For a concrete example, see the comments on this answer to one of my previous questions in a similar vein to this one; essentially, one can rotate the graph of 
$$y=\epsilon \cos(x)$$
for small enough $\epsilon$ exactly $45^{\circ}$ counterclockwise, and it satisfies the property.
