What does it mean, when one says that system has $N$ constants of motion? For example for an isolated system the energy $E$ is conserved. But then any function of energy, (like $E^2,\sin E,\frac{ln|E|}{E^{42}}$ e.t.c.)
is conserved too. Therefore one can make up infinitely many conserved quantities just by using the conservation of energy.
Why then one can usually hear of "system having $N$ constants of motion"? "System having only one constant of motion"?
 A: Maybe it is worth distinguishing independent integrals of motion from functions of integrals of motion? See equations (2) and (3) in my post. The number of independent constants of motion is limited with the number of independent initial data (if the problem is well posed).
EDIT: another way to understand it is to count independent degrees of freedom of the system.
A: Let us assume (for simplicity in this question) that the Hamiltonian H is time independent. Then any function f whose Poisson Bracket with H {f, H}=0 is a constant of motion. Also Poisson's Theorem is that if f,g are both constants of motion then so is {f,g} generating yet more constants of motion.
The clarification is that the functions f, g here define canonical changes of variable, so we are only interested in ones that replace the $p_i$ and $q_i$ with new coordinates $(P_i,Q_i)$. There are only going to be at most 2N of these.
The ideal arrangement is to cause as many of the $Q_i$'s as possible to drop out of the (transformed) Hamiltonian $H=H(P_i,Q_i)$, there only being N maximum available. So yes many "constants of motion" will be functions of one another (akin to having not only x(q),y(p) available as coordinates, but also x+y, $x^2$, etc), but one wants to use only those which lead to a simpler Hamiltonian.
A: There are seven fundamental additive constants of the motion in classical mechanics, these are the energy and the three components of momentum and angular momentum.  In other words, every constant of the motion, $C$, can be written uniquely as:
$\hspace{3cm} C=a_1E+a_2P_x+a_3P_y+a_4P_z+a_5L_x+a_5L_y+a_7L_z$
A proof of this fact can be found in Landau, Vol 1.
