Along with adding constants, an arbitrary function of existing conserved quantities will also be conserved. If $X_1, X_2, \dots X_n$ are all conserved, then $f(X_1, X_2, \dots X_n)$ will also be conserved for any function $f$. So really the conserved quantities should form a space, with some number of dimensions. The number of dimensions is the number of "nontrivial conserved quantities".
Any particular conserved quantity we examine is going to be a scalar that varies across this space. Any given state of the system corresponds to a point in the space, which doesn't move as the system evolves. Since the point doesn't move, the value of the scalar doesn't change, and so the scalar is conserved.
If the system has $N$ degrees of freedom (i.e. its phase space is $2N$ dimensional) then the dimension of the conserved space is also $2N$. Why? Conserved quantities are allowed to depend on the $t$ coordinate in general, so given a particular state at a particular time, we can just run time backwards to $t=0$, and we get the $N$ initial position coordinates, and the $N$ initial momentum coordinates. At any point in the trajectory, running time back to $t=0$ will give the same initial condition, so these $2N$ variables must all be conserved. (And the initial condition can vary any of these variables independently, so the space must have a full $2N$ dimensions.)
A coordinate transformation can't change the number of dimensions in a space, so there will always be $2N$ conserved quantities, though some of them may end up looking very complicated.