Most of the people here answered what antialiasing is, and a couple offered some theory. I could get into the details of that theory, algorithms used, but instead I'll discuss something that I don't think has been talked about in this thead: sub-pixel anti-aliasing.
Sub-pixel anti-aliasing, also known as ClearType nowadays, was actually invented many years ago. Apple used it on their old monitors for some games. The concept is simple. You take a pixel on the screen and divide it up into three sub-pixels. This is more effective on PDAs and LCD monitors, where each pixel actually is composed of tiny red, green, and blue cells in one of a couple different patterns that can be turned on or off to varying levels of brightness. In a standard CRT monitor, the color is more "sprayed" into the pixel, to put it simply.
If you have Windows XP around, turn on ClearType in the antialiasing options (I think it's in the desktop properties dialog somewhere). If you look close at the screen, you'll notice little colors around the text. This will be more apparent on a standard CRT monitor than a flat screen LCD monitor. Here's why you see the colors.
Imagine your pixel as a box like this: []. On an LCD, it's really more like this: [][][]. The cells inside the pixel are usually in RGB (Red Green Blue) arrangement, though other arrangements are also used on some screens. When you turn anti-alias a line, you'd typically have that pixel (all 3 sub-pixels) set to black, and the pixels to the left and right may be a shade of grey to have the illusion of the line being anti-aliased. This takes 3 pixels. However, with sub-pixel anti-aliasing, your horizontal resolution, anti-aliasing-wise, triples. Instead of using 3 pixels, you can have the middle pixel set to black and the left and right set to a shade of their color, for a very thin line, or that pixel can be black and the right-most sub-pixel on the pixel to the left can be set to a shade of its blue, and the left-most sub-pixel on the pixel to the right can be set to a shade of red.
Did that make sense? :/
Anyhow, if you use an LCD screen (laptop or flat panel monitor, or some PDAs), try enabling ClearType. Even if you have a CRT monitor, check it out. It's really nice, and improves the quality a bit, though in some cases you'll see some color poking out around the side
You can find more information and some examples of the pixel arrangements, as well as quality comparisons by doing a search on Google for "Richard Leader" and "ClearType". Somewhere, he has a site with some nice examples and detailed information.
That ended up longer than I thought it would.