This rule is clearly explained on the back of the immigration declaration form which every visitor must personally fill out[0]. It is, in fact, item number one.
Yes, China is a totalitarian shithole. But then again some democratic countries like Japan have similar "register at local police station" rules too, so I'm very surprised that someone who spent a decade in Asia would be unaware of it.
[0] http://sydney.chineseconsulate.org/eng/gdtp/P020071009492059...