To understand negative temperatures, it is best to consider the inverse temperature $\beta \equiv (k_B T)^{-1}$, which appears in the expression of the partition function $Z\equiv \sum_n e^{-\beta E_n}$. A system 1 is hotter than system 2 (i.e., if brought into thermal contacts, heat will flow from 1 to 2) if $\beta_1 < \beta_2$.
For systems with an energy spectrum that is unbound upwards (as is the case for example for the kinetic energy of particles in a gas), the lowest possible value for $\beta$ is zero, i.e., the hotest possible temperature in a gas is $T=\infty$, in which all states are equally populated, irrespective of their energy.
The situation is different however for a system possessing an energy spectrum which is bound upwards (for example an assembly of spins in a magnetic field). In this case, any value of $\beta$ between $-\infty$ and $+\infty$ is possible. A negative value of $\beta$ corresponds to thermodynamic states in which the microscopic states of low energy are less populated than higher energy states (this the situation of population inversion created in lasers and enabling coherent radiation). So a system with negative temperature $T$ is actually hotter than any system with a positive temperature. The apparent paradox only lies in the fact that the natural quantity for measuring "hotness" is $\beta$ rather than $T$.