I'm not sure if this applies to all (if any) multi-player servers. I noticed that if two Player Entities (players) are on the same block(s) and not moving, the sound of walking will play. It also varies on speed (i.e. crouching, walking, sprinting speeds).

Shortened Version: If two non-moving players are on similar blocks, it makes the walking sound.

Also, the walking sounds take into account of what block your walking on (two players on a grass block makes the "walking on grass" sound)