i'm not that much into animation, specialy caracter anim, but i think you can set up a path constrain on your walk cycles via simple spline, try google it, i remember reading something about it.

---

The secret of creativity is knowing how to hide your sources.
-Albert Einstein

Path constraints are awesome, especially with cameras. But they're not exactly the easiest to work with in real time, and it's especially had to do subtle movements with them.

---

Two options.

1.With character studio. If you create a looping on the spot walk cycle and copy the keys to make the character walk for your desired timeframe. Then add a new animation layer and select both feet and the centre of mass. then key the whole character moving forward with linear interpolation. You may need to adjust either the distance he travels or the speed of the steps to get it to look like he is making contact with the ground and not sliding.

2. create a walk cycle moving forward making sure to key all the tracks for the centre of mass. horizontal, verticle and rotation. even if it isnt going to rotate.
save it out as a bip. and load it into motion mixer as a clip. then you can loop them relative and play with time stretching etc..

Other than that you are probably up for some manual keyframing of the entire animation which is most probably going to be the best method as some fancy footwork is usually going to look better and more natural if you animate it straight ahead.
I always just remember that the 2d guys can't even preview it. at least we can see what our timing is going to look like at each point of the process.

---