That is handled with Inverse Kinetics (IK). The end of the leg chain follows a point that is glued to world space, whatever the rest of the body is doing that foot is stuck to that point.
In biped its called "planted keys"
(Biped Menu > Key Info).
They enable you to plant the feet on the ground plane then use "sliding keys" to move them backward while they stay locked to the ground plane.
I normally suggest doing a walk cycle with the character moving forward through the scene, its much easier to get a sense of the walk that way. You miss a lot when its stuck in place. Then zero out the forward motion to create an in-place walk cycle.
By switching the pivot point in the feet from the heel (on contact) to the toes (on sliding and release) you get a pretty convincing roll to the foot.


The red dot on the bottom of the blue foot indicates where the planted key pivot point is positioned, this is the point that sticks to the ground.
While you're working with the character moving through the scene, you can also toggle on "in-place mode" (
under Biped menu > modes and display target looking button) to see how it will look in-place but you can turn it off to work on the cycle easier.
This is what it looks like when you turn on in-place mode or zero out the horizontal movement:
You can also save out the animation, load it into motion mixer and filter out the horizontal motion to get a walk cycle that is in place. Which is handy if you're working with mo-cap clips or animations you've done on another rig and want to transfer over to this one.
So yea Planted Keys...