Shimano PF-M545 pedals Mavic Alpine All Mountain Shoes how to fit the cleats
Turns out that there was a male screw thread inside the female and I needed an allen key to get it out. (I had to go to bike shop to learn that, though.)

After that point the rest was clear sailing, following the instructions closely, and watching some online video tutorials about it.