Before cycling your animation you will need to make the end pose exactly the same as your start pose - though further along in the walk. Copy over the start pose by selecting all of the rig's controls (just use the built in "Select All" button for the Basic Guy rig), middle click-holding on the start pose's frame in the timeline, dragging to the frame the end pose will be on, and hitting "s" to key it.
The problem now is getting this end pose to where it should be at the end of the cycle.
Select all of the controls that will need to translate forward: the hip, feet, and knee controls. They should be the same for the Basic Guy rig. Drag the Translate Z forward until the pose is to about where you think it should be.
From here on you will want to use the carrot keys (">" and "<", the hotkeys for switching between keyframes) to switch back and forth between the end pose and the pose before it so you can line up the end pose accordingly. Note that you may want to temporarily turn auto-key on if it isn't already so Maya will save your adjustments when switching between poses. If you're using the contact method for the walk cycle, a good way to line up the poses is by using the back foot as a reference.
Zoom in and line it up as close as you can but don't worry about being 100% exact.
When you are finished lining up the end pose, open up the graph editor and select all of the controls and their channels. Go to Curves->Post Infinity->Cycle with Offset. This will loop the selected channels and add offset when necessary (in this case it will add offset to the Translate Z channels of the hip, feet, and knee controls). To see how your animation loops in the graph editor, check View->Infinity. Your graph editor should look something like this:
The "infinity curve" will automatically update if you make changes to your animation. However, you will need make sure that the start/end poses are always the same if you decide to change one of them. Also, note that the tangents are a bit broken where the start and end pose meet. You can just go ahead and fix this manually.
