Full Screen Anti-Aliasing (FSAA)
Most people today know what a pixel is, an abbreviation
for "picture element," the small square dots that monitors
use to display images (IBM once persisted in having its employees
call them "pels" though the term never caught on). Because
monitors use combinations of these small squares in image display,
there are circumstances in which the pixels of the image are as
or even more noticeable than the image itself. As people's standards
for computer imagery have increased over they years, people have
likewise become more aware of imperfections in computer display
technologies. While "pixilated" has become a catchall
term for this in the vernacular, "pixilation" actually
refers to a variety of phenomena.
For example, one kind of "pixilation" (as
it is commonly used) refers to imperfections in JPG pictures on
the internet, which appear due to how they are compressed to make
for shorter download times. These are known technically as "compression
artifacts" and are actually often far larger than individual
pixels in size, yet they are still described as pixilation by millions
of users.
Another type is less well known. Aliasing, a term
originally borrowed from sound and oscilloscope technology, occurs
when high frequency data is sampled too slowly. There is one example
of this which you see all the time: often on television when someone
wears a shirt or tie with very thin stripes on it, a strange shimmer
representing the full spectrum of colors will appear. This is called
the moiré effect. It comes from the lines on your television
being too thick to accurately display the thin detail of the tie--yet
that detail must be displayed.
Likewise, pixels are often too large to accurately
display many details in computer games--that is what happens when
you try to represent curves, waves, diagonal lines, and all sorts
of shapes using nothing but small squares (as pixels get smaller
at high resolutions, this problem is diminished as well). These
are referred to as "jaggies" or aliasing, but are often
lumped under pixilation as well.
Jaggies most often occur when two distinct objects
with different coloring intersect; for if their textures are similar,
their boundaries will be camouflaged by it. That is why jaggies
are especially noticeable in older games with often limited textures
than in newer games with high definition textures, and in games
with lighter color palates than those with dark.
But there is a way of getting around the limitations
of square pixels. You might not be able to color only half a pixel,
but you can simulate the same thing by giving a pixel half of the
desired color. By using varied amounts of color (provided there
is enough colors to pick from, in the days of 256 color displays,
this was much harder to accomplish), nearly any fraction of a pixel
can be represented. This is called anti-aliasing.

While at first glance, it might appear that anti-aliasing
is simply blurring the line. It is not. Blurring would imply a lessening
of detail, on the other hand, this is an increase in detail in that
the line (if not magnified several times for clarity) would appear
much more defined than it would otherwise.
There are two ways in which anti-aliasing is currently
accomplished, depending on your video-card's manufacturer and settings.

Super-sampling anti-aliases by creating an image at
a higher resolution than that which your game is set for, and then
"samples" the image down to the desired size, using the
extra information (in the above example, twice the resolution means
four times as many pixels are rendered!) to eliminate the jaggies.

Multisampling, on the other hand, combines slightly
different images that are rendered separately on the subpixel level,
each adding more information to further anti-alias the image. Any
number of samples can be used, though most video cards only support
2x or 4x multisampling, while some, such as nVidia cards, offer
more complex forms of multisampling which purport to give added
visual quality with less of a cost in speed.
Speed is the largest reason to not use anti-aliasing
(though as it is a newer feature to video cards, typically only
the fastest cards on the market have even supported it until very
recently). As the video card is required to do more work--especially
in super-sampling modes where it has to render four to eight times
as many pixels--the FPS that it is capable of producing at a give
resolution will be diminished proportionately.
However, newer cards are increasingly having anti-aliasing
integrated as a key component rather than an afterthought, as well
as using more innovative multisampling techniques, so the overhead
for full screen anti-aliasing (FSAA) is diminishing.

Spidey with FSAA and without

Mouse over image
for FSAA Version
FSAA has a tendency to make everything look shiny
and new--even older games that have been sitting on the shelf for
a while. Not just in that they look better, still shots can be deceiving--the
illusion of 3D is actually heightened by FSAA when you see it in
motion, making a card capable of it a solid investment.