The official word from Apple on this is that you need to reinstall the OS.
If I remove one of the bundled
applications, such as Safari or Mail,
how can I get them back?
You must
reinstall Mac OS X from the MacBook
Air Software Reinstall Drive to
restore bundled applications. To bring
your computer up to date, use Software
Update after Mac OS X finishes
installing.
Another Mac - Before reinstalling the OS, I'd check with a friend that has a Mac and see if you can copy the app from another Mac.
Reinstall to Another Drive - Rather than reinstalling the OS to your main MacBook Air drive, you could try reinstalling to another drive (e.g. external USB drive). Then you could simply copy the app to your main MacBook Air drive.
Standard Reinstall - If you have to reinstall the OS over your current system, it isn't as painful as on Windows if that is what you are used to. You can keep your user accounts and settings so it may not be too painful.