Anti-Aliasing is a hardware algorithm that helps to smoothen out textures in 3D games and applications. It's also referred to as bilinear(sometimes trilinear) filtering. But I think what you're referring to is Full Scene Anti-Aliasing...
Full Scene Anti-Aliasing is a hardware algorithm that helps to smoothen out jagged edges (called "jaggies") of 3D polygons. It's the most effective method of getting rid of jaggies and the "crawling" effect present in most 3D games. Most modern video cards have FSAA (Voodoo 5, Radeon, GeForce series) implemented. The GeForce cards use super-sampling for their FSAA, which basically renders a scene in higher resolution, then scales it down to the output resolution. For all it's worth you might as well as play at a higher resolution altogether. The Voodoo 5 uses a different method(multi-sample) where it takes multiple samples of the same scene and shifts each of them slightly on a sub-pixel level and merge them together to produce the final image. The Voodoo 5 FSAA tends to produce higher quality graphics. 4X FSAA on a Voodoo 5 will eliminate virtually all jaggies. However, FSAA comes with steep performance drops, even with hardware acceleration. With 4X FSAA frame rates will drop by 3/4, because it has to render the same scene 4 times. FSAA on GeForce cards also produce heavy performance loss, because you're rendering at a higher resolution. Most modern videocards have the processing power to do FSAA but only at lower resolutions (< 800x600).
Stevenlcw, go to the screenshots forum and take a look at two different threads entitled Quake 2 and Raziel-Gauntlet Legends Screens. These will give you an idea of FSAA in action. Of course any other of the fine screen shots will show this as well. Believe me, FSAA is well worth it.