Anti alliasing calculates the grapics for a higher resolution than you actually use, and then reduces the resolution again, taking the average values for the colours in the different high res pixels. So if you're running in 1024*768, it may calculate 2048*1536 pixels, and then averages over each 4 pixels.
The result is that interfaces between 2 objects become much smoother. Instead of having 1 pixel on your screen belonging to one object (lets say a unit) and the next pixel belonging to another object (lets say the terrain), both pixels may now belong to both the unit and the terrain, making the unit look much better 'rounded' instead of squared.
A pretty good example is actually an ordinary pdf file. Open with acrobat, take a screenshot and enlarge that screenshot in paint. You will then see that the letters have various grey colours (unlike these boards).