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.