Is there any sort of classification of (say finite) groups with the property that every subgroup is normal?

Of course, any abelian group has this property, but the quaternions show commutativity isn't necessary.

If there isn't a classification, can we at least say the group must be of prime power order, or even a power of two?

These are called Dedekind groups, and the non-abelian ones are called Hamiltonian groups.  The finite ones were classified by Dedekind, and the classification extended to all groups by Baer.  The non-abelian ones are a direct product of the quaternion group of order 8, an elementary abelian 2 group, and a periodic abelian group of odd order (or all of whose elements have odd order).

Periodic abelian groups all of whose elements have odd order can be quite complicated, but the finite ones are direct products of cyclic groups.

Your example does not have the property that all of its subgroups are normal when n ≥ 4.  The subgroup generated by x1*x2*x3 is not normal, since (x1*x2*x3)^x4 = (ax1)(ax2)(ax3) = ax1*x2*x3, but x1*x2*x3 has order 2.  For n = 3, your group is Q8 x 2, and so is Hamiltonian.

The cyclic group of order 6 and the direct product Q8 x 3 are two groups of non-(prime power) order with every subgroup normal.
