Anti-aliasing smooths the picture on screen to produce a better image (less jagged lines or "jaggies"). If you like things being pretty, you want to turn it on. There's varying levels of it (2x, 4x, etc.) that scale for even better image quality, but they're also more taxing on your system.
To put the 2600XT thing into perspective, if you like all the eye-candy and turning your resolution up hgiher, then that card isn't for you. It does well at lower resolutions, but once you start turning things on like Anti-aliasing, then it struggles, largely because of the limited memory bandwidth (it's only 128-bit, making it closer to an x1650 rather than an x1950, or a 7600GT if you're an Nvidia person).
If memory bandwidth where the only issue then raising the memory clock would solve that, it doesn't.
AA smoothes out jagged edges on games, its impact depends on what type you use, inaly there are SSAA and MSAA, SuperSampling simply renders the image at 2x2 in each direction or 4x4 in each direction, and its 4x AA and 16x AA relatively.
MultiSampling is my prefered option which uses something I have never understood, but its very nice towards performance and I find 4x MSAA aslong with that setting I cant remember atm set to multisampling usually gives me 100% crisp pictures.