Oi, fast resolution and lots of posts for one day!
Well, I strongly recomend turning record on (if it isn't working for you, perhaps you may need to set it on in user defaults (set it on, and use ctrl + u), or perhaps you may need to select the objects first).
The record button is on the right side of the timeline window, and looks like a red dot ('record'). Set it to add/remove frames (or something like that).
Remember it affects both objects moved and armatures (probably plenty others too, but I didn't test). Note that edit mode naturally still affects the mesh, for all frames, without changing the position.
Congrats on your animation, just before I released a new tutorial (look for it in 2-4 days) about using blender (modeling, texturing, animating, and exporting, on the theme or guarenteed knowledge).
Might I ask why you are creating a marine model? The military mod (currently still in developement) features a very nice fully animated marine model.