Anti-aliasing has two meanings with graphics. The first kind has to deal with textures applied to polygons. Textures are applied to add more detail than would be possible using a pure polygonal approach. The problem with that is that sometimes the textures are smaller than the size of the polygon they're being applied to, so the texture is stretched. When this happens the actual pixels that make up that texture are enlarged, causing it to look pixelated. Anti-aliaising of the texture, also called "filtering" comes into play. It basically smooths out the pixels (often by averaging colors of nearby pixels) to create something that isn't as 'harsh' to look at.
The other form comes in the way of removing the "jaggies" that appear when objects on the screen at odd angles. It creates what looks like stair-steps and at lower resultions (640x480, 800x600) can be unpleasant to look at. Anti-aliasing of edges removes these in two possible ways... The first creates multiple frames of the current frame. These are then overlayed to eliminate the jagged edges. This method is called "Multi Sampling." The other method simply renders the scene at a higher resolution (ei. rendering at 1280x1024 for a 640x480 scene) and scaling it back down. This is called "Super Sampling."
