If an operator commutes with the Hamiltonian of a problem, must it always admit degeneracy? It appears that not necessarily. For example, the parity operator commutes with the Hamiltonian of a free particle as well as that of the 1-D linear harmonic oscillator. But in the former case, we have two-fold degeneracy for a given energy and no degeneracy for the latter. Does it mean that $[P, H]=0$ is not the sufficient condition to have degeneracy in the energy eigenstates?
If an operator commutes with the Hamiltonian of a problem, must it always admit degeneracy?
No. The identity always commutes with the Hamiltonian, yet we don't generally find all energy levels to be degenerate.
Does it mean that $[P,H]=0$ is not the sufficient condition to have degeneracy in the energy eigenstates?
Yes. It is not a sufficient condition.
Let $A,B$ be any two self-adjoint operators that commute, $[A,B]=0$. Define the eigenvectors of $A$ through
Now we prove that $B|a\rangle$ is also an eigenvector of $A$: $$ A(B|a\rangle)=BA|a\rangle=a(B|a\rangle) $$
Welp, that was easy.
We could naively say that $a$ is degenerate, because both $|a\rangle$ and $B|a\rangle$ have the same eigenvalue, but this breaks down if $|a\rangle$ is an eigenvector of $B$, because in that case $B|a\rangle\propto |a\rangle$ and there is no degeneracy!
Therefore, if $|a\rangle$ is not an eigenvector of $B$ we find that $a$ is degenerate, with at least two eigenvectors, $|a\rangle$ and $B|a\rangle$. If $|a\rangle$ is an eigenvector of $B$ we can't conclude anything about the degeneracy of $a$.
In the case $B=\mathbb I$, we obviously have $[H,B]=0$, but as any vector is an eigenvector of $\mathbb I$, the fact that these operators commute gives no information about energy-degeneracies.
In the case of a free particle, the parity operators acts on kets by changing the sign, $P|\boldsymbol p\rangle=|-\boldsymbol p\rangle$, which is not proportional to $|\boldsymbol p\rangle$ (a.e.), and therefore we do have the two-fold degeneracy you said.
If there exist two non-commuting Hermitian operators $A$ and $B$ which both commute with the Hamiltonian, then the energy eigenvalues will in general, but not always, be degenerate. The exceptions only occur when $A$ and $B$ have a common eigenstate which is also a zero-eigenvalued eigenstate of their commutator.
According to Noether's theorem, for any symmetry of the system, there exist some conserved quantities that commute with the Hamiltonian, one for each continuous parameter of the symmetry transformations. If such symmetry transformations of a certain kind don't commute with each other, which makes the corresponding conserved quantities noncommuting, then, according to the statement above, there will generally be degeneracy in the spectrum. As an example, consider a one-particle system with a spherical potential. Because of the isotropy of the system, the three components of the angular momentum are conserved. And because those components don't commute, the energy levels are degenerate except for those with zero angular momentum.
In your harmonic oscillator example, there's no degeneracy in the spectrum because you can find no conserved quantity that fails to commute with the space inversion operator.