Yep. Linux has run on the Mac for ages, ever since PowerPC support was added to the kernel. And if you have a really old pre PowerPC Mac, the Linux m68k project should cover your needs.

More relevant to the current situation, you can go two routes. You can boot the Mac into legacy mode (used by BootCamp to support Windows), and Linux will just use the traditional MBR boot loader and work as it does on any BIOS based machine. Or you can go the EFI boot route, and I'd recommend rEFIt as a good boot loader for letting you get into the EFI side of the machine if needed.

For specific hardware info, the Ubuntu Wiki is a good resource. The new Air is too new for their site, but hardware wise is very similar to the most recent Macbook (non pro) model. Info for it is here.

Specific to the Air for install, you will need a USB DVD drive, a properly set up USB thumb drive, or an SD card with the proper boot files for Linux.

And thankfully, since it's a real notebook, you get a proper Core 2 Duo CPU instead of an Atom netbook processor. Should keep those compile times down when doing heavy coding on the machine.