How does compass calibration work? I am wondering how compass calibration works / why e.g. drawing an 8 or rotating the phone to all 3 axis works (or at least shall work) - I mean I would understand the calibration process, if an application would say me: Point to north, then press that button down there, but you can start at basically zero knowledge for the app, just by rotating your phone! How is that done? Also, do I need to enter a special calibration mode or can I draw these figures (like the 8) directly in Google Maps? How does Google Maps know that I am not just really moving the phone but want to calibrate the compass? Thanks for any hint!
The purpose of calibration is to figure out how to compensate for how the components in your phone (screws, speaker magnets, etc.) interfere with the measured magnetic field. 

The calibration process is based on the fact that you can separate the internal and external contributions to the magnetic field by looking at how the field changes as the phone is rotated. For example, in one orientation the magnetic field from the magnet in the speaker will add on to the Earth's field; but when the phone is oriented in the opposite direction, the two fields will partially cancel out. 

As you wave the phone around, the magnetometer records how the magnitude of the measured field changes and uses this to calibrate the x, y, and z magnetic field sensors. See geometrikal's answer to a similar question for more details on this process. Note that this calibration does not let you compensate for the influence of other external objects (e.g., your refrigerator) on the magnetic field.

Regarding the implementation in Google Maps: I believe that Google Maps has no control over the compass calibration because there is no such functionality  in the Android API. The magnetometer is probably calibrating itself continuously, and Google Maps is just asking you to rotate your phone so that the magnetometer can collect the data it needs to get an accurate calibration. 

In other words, you can calibrate your compass any time the magnetic field sensor is being used just by waving your phone – there is no "calibration mode".