Marek posted a set of seven new Radeon Gallium3D MSAA patches on Wednesday evening for R600g that provides initial MSAA support for Radeon HD 4000 "R700" series GPUs. In addition to the new MSAA support, there's support for compression of multi-sample anti-aliasing color-buffers for R700/Evergreen. The color-buffer compression should save a lot of bandwidth now when using MSAA. In addition to this work, he's landed some minor MSAA-related fixes.
The R600 Gallium3D driver now supports multi-sample anti-aliasing for Radeon HD 4000/5000 series GPUs with the forthcoming Mesa 9.0. MSAA levels of 2x, 4x, and 8x are currently supported by the open-source AMD Linux graphics driver. Mesa also currently supports Morphological Anti-Aliasing.
Marek's latest MSAA patches for Radeon can be found on mesa-dev but soon will likely be merged to Mesa Git master.