My team used a reference picture like
http://bobbypontillas.com/blogpics/walkplan.jpg to make a walk cycle, which would be 24 frames (24 frames/sec.) that when repeated creates a smooth walk.
The picture is really helpful because it shows you the positions the legs should be in at each frame. All you do is go to the frame, position the legs, make a keyframe and go on and do the same for the next. This should create smooth transitions between each leg position.