Creating an Action
The walking animation will be a cycle, meaning that you’ll only be animating one step (it happens in place, so the character won’t move across space; that will happen later), which will then be repeated over time. As you’ll be repeating it using the NLA Editor, you need to create an action that you can load later.
Each object has different actions, so make sure you have the rig selected in Pose Mode before you create an action. If you are in Object Mode, selecting the rig will create an action for the container, not for the individual bones that you need.
Open the Dope Sheet Editor and switch to the Action Editor Mode. On the header, if you haven’t animated anything, there will be a field in which you’ll be able to create a New Action. Press the New button and the new action will be called (surprise!) Action. Rename it to something intuitive such as Walk_Cycle.
Now, every keyframe you set for the bones in the rig will be a part of the Walk_Cycle action.
Caution
If you create more than one action, remember that any datablocks not in use when you close Blender will be deleted. Each object can only use a single action at a time, so if you want to make sure the rest of the datablocks are saved, press the F button next to their names so they have a “fake user”; this will prevent them from being deleted when you close Blender.