We consider the general problem of determining exactly when a classical Hamiltonian H = Sigmag(ij)(x)p(i)p(j) + V(x) in n dimensions admits a constant of the motion that is polynomial in the momenta. If the associated Hamilton-Jacobi equation admits an orthogonal separation of variables., then it is possible to generate algorithmically a canonical basis Q, P where P-1 = H P-2,..., P-n are the other second-order constants of the motion associated with the separable coordinates, and {Q(i), Q(j)} = {P-i, P-j} = 0, {Q(i), P-j} = delta(ij). The 2n - 1 functions Q(2),..., Q(n), P-1,..., P-n form a basis for the invariants. We show how to determine for exactly which spaces and potentials the invariant Q(j) is a polynomial in the original momenta.