I think you were closer to the answer than you realize. In this "Maya Basics & Newbie Forum", there is a thread "HOW DO I RENDER A MOVIE" by mtmckinley (at the top). I believe he explains how.

After you have your animation rendered and saved, you'll need to use another program to convert the frames into a video file. ckyuk mentions in the thread a program called videomach for that purpose. Just read through the whole thread.