Summary

Got it working with a twin DVI dual-head setup, but with many issues.

Supported driver is binary, buggy and unstable and hasn't been updated in two years.

The supported kernel module only works on early 2.6 kernels.

There is an unsupported patch to compile this module for 2.6.1x kernels, but I haven't gotten it to compile properly on my Ubuntu-5.10 (kernel 2.6.12-9) system.
Xinerama mode was very buggy and the entire xserver would crash often.
So, I can't drag windows between displays (xinerama is disabled because it is nearly unusable), don't have any acceleration since the kernel module won't compile (although this could be my fault), can't pivot my displays without restarting X (no xrandr support), and I periodically come back to work to find that my mouse has frozen because of some conflict with xscreensaver.
Also, when I say "restarting X", I mean rebooting because there's this issue that causes my secondary display to go blank if I try to switch to terminal mode and then back again or restart X. The only way I can get it to recognize the second monitor again is to reboot.

Matrox has promised a driver update in the next month or so, but I'm not holding my breath. Buy something that is better supported.

http://www.tuxx-home.at/projects/mtx/latest/
http://forum.matrox.com/mga/viewforum.php?f=2&start=0