they must both be of the same degree, say degree $n$. $P(x)=x^n+a_1x^{n-1} + \ldots + a_n$ $Q(x)=x^n+b_1x^{n-1}+ \ldots + b_n$ equating the $x^{n(n-1)}$ terms in $P(P(x))$ and $Q(Q(x))$, we have $a_1^{n}x^{n(n-1)}=b_1^{n}x^{n(n-1)} \rightarrow a_1=b_1$. we can continue in this manner, equating the $x^{n(n-i)}$ terms for $i \in {1, 2, \ldots n}$ to show that $a_i=b_i$ for those $i$, which means $P=Q$.

Also posted here http://www.artofproblemsolving.com/Forum/viewtopic.php?f=36&t=237348

Sorry for the revival, but the above solution does not seem to be quite correct. The fact that $a_1^n = b_1^n$ does not imply $a_1 = b_1$, especially when working with complex numbers.

http://www.imomath.com/index.php?options=627&lmm=0