To generate a normal map, you have to be running Maya 6 or later. This version has all the appropriate tools that allow you to generate and apply normal maps.
There's a plug-in available for previous versions of Maya, called RayDisplace, that will generate normal map data within Maya, but it's a bit unstable. There are also stand-alone utilities from the major card manufacturers that process the high-polygon model data to produce the normal map data. But Maya 6 is the first in-software implementation of normal mapping.
In addition, your video card must be able to support normal maps. Maya will generate the data regardless of your graphics card's abilities, but without the proper video card, you won't be able to use Maya's High Quality Interactive Render option to view the maps.