Blind Carrier Synchronization
One approach not yet mentioned is frequency multiplication by a factor of the number of phase positions used followed by a PLL for noise reduction and then a frequency divider by then same factor.  The reason for this is when you multiply the frequency by N, you also multiply the phase by N. If the phase positions are selections of $2\pi/N$ (or those with any fixed offset), then multiplying the phases by N results in a consistent phase angle versus time, which then results in a fixed frequency tone that a PLL can lock to.

For example with BPSK (2 phase positions) a simple squaring will produce a specular component at 2x the carrier frequency since changing between 0° and 180° will result in changing between 0° and 0° (at twice the frequency) after doubling.  With QPSK (4 phase positions) you need to raise the signal to the 4th power (which will quadruple the frequency, and the phase).  The reason for the PLL is that any AM components (through pulse shaping or QAM modulation) will result in other lower level frequency components that the PLL will essentially filter out. 

To answer your question as to what is so special about raising to the Nth power is that you basically raise to a sufficient enough power such that the modulo phase variation of the result is equivalent to small angle PM (which has a dominant carrier) in contrast to BPSK for example which has complete carrier suppression with equiprobable data.