It is my second day using Blender so I am positive some of the following terminology is wrong.
I ran into this exact same issue. I don't quite understand why, but I think the caveat is that Blender does not let you have a single "Action" do different things to more than a single "Blender Object".
In the Action Editor, when you use Shift + RMB to select two meshes and key I to insert a keyframe, it links the two Blender Objects to that Action - which is a single transform. This moves the secondary Blender Object inside of the primary Blender Object since they now have the same transform.
What I believe Blender wants you to do is instead create this Blender Object called a "Pose?", which is a hierarchy tree of Armature Bones. Your bones get attached to the mesh through parenting and then moving the bones in Pose Mode will move the mesh.
The pose is now the thing that you move around to create the desired animation. You enter a special Pose Mode (Ctrl + Tab) to interact with the bones. Lastly there is a special Pose Tools section in this panel called the Toolshelf (w/ mouse in 3D Viewport, key T to toggle open/close). In the Pose Tools section, you will see Keyframes: Insert | Remove, and this time around the Action Editor will save and display all the different transforms for the armature.
You can find a few sample rigs online which showcase the relationship between the armatures and meshes. I will give the disclaimer that I know next to nothing about modeling, and I am sure I have botched some of this explanation.
