On what principle did Google's DeepMind learn to walk?

The full method is explained in the paper Emergence of Locomotion Behaviours in Rich Environments by the DeepMind team.

Quoting from that paper:

Using a novel scalable variant of policy gradient reinforcement learning, our agents learn to run, jump, crouch and turn as required by the environment . . .

So to answer your question, the researchers used a policy gradient method.