In the game world, everything is defined by polygons. These polygons have theoretical straight edges, however, pixels are vertically uniform squares. So any time the edge of one of these polygons is anything but perfectly vertical or horizontal, you get a 'stepping' effect creating a jagged edge like a saw. Anti-aliasing takes everything on your screen and runs a pass over it, splitting those pixels, which smooths the edge. The 1x, 2x, 4x, 8x, etc. Is a count of how many passes it makes on the image, how many times it splits those pixels, and how smooth the edge is.
The higher, the better the image. However, it's an intense process and short of texture quality I can't think of a graphical setting that affects your framerate more. Start everything off maxed and if you get a low framerate, just decrease things incrementally.
FYI - Turning shadows (Shadows, not Shading) to the lowest setting is a good boost to framerate and you honestly won't notice the difference after ten minutes of playing.
Edit: Also, you are not limited to what the game's configuration limits you to. If you find that with everything maxed you still run at a constantly high frame rate, then you can hop into the NVidia control panel and enhance the application settings through profiles. For example, SLI32x Antialiasing with Supersampling makes World of Warcraft into a piece of art.
