USAJMO

We claim that the answer is $|a|=|b|$ .
Proof: $f$ and $g$ are surjective because $x+a$ and $x+b$ can take on any integral value, and by evaluating the parentheses in different order, we find $f(g(f(x)))=f(x+b)=f(x)+a$ and $g(f(g(x)))=g(x+a)=g(x)+b$ . We see that if $a=0$ then $g(x)=g(x)+b$ to $b=0$ as well, so similarly if $b=0$ then $a=0$ , so now assume $a, b\ne 0$ .
We see that if $x=|b|n$ then $f(x)\equiv f(0) \pmod{|a|}$ , if $x=|b|n+1$ then $f(x)\equiv f(1)\pmod{|a|}$ , if $x=|b|n+2$ then $f(x)\equiv f(2)\pmod{|a|}$ ... if $x=|b|(n+1)-1$ then $f(x)\equiv f(|b|-1)\pmod{|a|}$ . This means that the $b$ -element collection $\left\{f(0), f(1), f(2), ... ,f(|b|-1)\right\}$ contains all $|a|$ residues mod $|a|$ since $f$ is surjective, so $|b|\ge |a|$ . Doing the same to $g$ yields that $|a|\ge |b|$ , so this means that only $|a|=|b|$ can work.
For $a=b$ let $f(x)=x$ and $g(x)=x+a$ , and for $a=-b$ let $f(x)=-x$ and $g(x)=-x-a$ , so $|a|=|b|$ does work and are the only solutions, as desired.
-Stormersyle