Recently I got a MacBook Air, but it wasn't within my budget to get the bigger SSD. The standard SSD is advertised as 128 GB. In practice, this means 112 GiB, so I went looking for additional ways to get some extra storage space.
First and most cheapest, you can get an external harddisk. On one hand, it's very cheap. On the other hand, you have to remember taking it with you, and it's another wire and another device on your desk.
As an extension to that, there's the various wireless external harddisks. This Lifehacker article lists a few: Add Wireless Storage to Phones, Tablets, and Laptops with Wi-Fi Drives.
There's a number of USB-sticks that are so small, you can just leave them in. Here's a nice list of them:
Of these, I really like the Verbatim Store 'n' Stay because it seems the smallest of the bunch.
There's also a number of solutions that use the SD-card slot. They're basically adapters that take a micro-SD card. They're sized such that they sit flush with the outside of the MacBook.
Of these three, I am now testing the last one, and it sits perfectly flush with the MacBook Air's chassis:
I've got it fitted with a 16 GB micro-SD and it seems to work fine. There is no loss of speed noticeable, when comparing with the micro-SD-to-standard-SD-adapter that came with this card.