It’s possible to save the normal map in only two channels because of the fact that you know that the normal will be of unit length and pointing out from the surface. The technique is called hemisphere remapping and uses the following formula to unpack the third component from the two you saved in the normal map:
N.z = sqrt( 1 – N.x*N.x – N.y*N.y );
Because of the extra operations to get the third component, this method might not always be faster. And this method only works for tangent-space normals with unit length (but this is often the case).
Nvidia recommends the following texture formats to store the 2 channel normal map:
D3DFMT_V8U8 in DirectX
GL_LUMINANCE8_ALPHA8 in OpenGL
More information can be found in this GPU programming guide in chapter 4.11: