Some cleats are purely road and are not practical for any purpose other than racing or pseudo-racing, since they project from the sole and make walking difficult. All off-road, i.e. recessed cleats, can on the other hand be used for any purpose: mountain biking, touring, commuting, shopping... since many of the shoes that accept these cleats are also good for walking.
This is the original SPD concept and so much more versatile that I’ll not say anything more about the several incompatibly different road-only designs that Shimano have experimented with, apart from noting that SM-SH71 is one (which can also be used with some early designs of original SPD pedals).
All that follows is concerned only with the more versatile recessed cleats and the pedals that accept them. When I write below: ‘all SPD pedals’, that’s what I mean.
Originally there were just two SPD cleats: SM-SH50 was the standard single-release cleat (twist outwards only) and SM-SH55 offered multi-release (twist any direction you like and less force required), which is best for beginners and light riders. SH51 was an early (1995) improvement on the original SH50, and remains the current standard single-release cleat that fits almost all SPD pedals.
The exception is PD-M858, a race-special MTB pedal introduced in 2000 along with its own special cleat (SH52) that nevertheless also fitted pre-existing pedals. This pedal was quietly dropped in 2002 in favour of a new MTB racing pedal (PD-M959) that works with the usual SH51 cleat but not SH52, which nevertheless remains in Shimano’s catalogue for the benefit of anyone who bought M858.
The existing multi-release cleat didn’t work with the new-improved M959, which didn’t matter much as long as those improvements were only for MTB racers. But as the new pedal binding design trickled down to cheaper models it became necessary for Shimano to offer a compatible, new-improved, multi-release cleat, which is SH56. It fits all earlier SPD pedals except M858.
So it’s simple: use any SPD pedal (except old M858) and either SH51 or SH56, depending on whether you want standard or easy release.
This was first published in the June / July 2012 edition of CTC's Cycle magazine.