Should I keyframe every bone in the rig at every instance, or just the bones moving?
Short answer: Either is fine. 

Adding keyframes on more bones than needed can make the .blend file larger, but it is quicker to select all bones and add keyframes. Also, adding keyframes to all bones means that if you accidentally move a bone you do not notice while animating, the motion could be messed up and you may not notice.