First we had to disconnect all the cables around the drive, as well as remove the little black strip to the left of the notebook and the ports in the upper left.

It appears to be the MacBook Air's speaker

There are four screws that hold the hard drive in, three of which are visible. The fourth is underneath a removable piece of black plastic stuck to the screw:

With all of the screws out you can actually lift the bracket that holds the hard drive and pop the hard drive out:

The MacBook Air hard drive is a 1.8", 5mm thick PATA drive from Samsung. It features a 8MB buffer and spins at 4200RPM. There is no accessible SATA interface on the motherboard, clearly for space constraints. Instead of a standard PATA connector Apple uses a 40-pin ZIF (Zero Insertion Force) connector, which Samsung offers as an option on its drives.

From left to right: 1.8" MacBook Air drive, 2.5" standard notebook drive, 3.5" desktop drive

The drive itself is a Spinpoint N2 and carries the model number HS082HB. It looks like replacing it with a 1.8", 5mm thick SSD should be possible as long as you opt for the 40-pin ZIF connector. It looks like Samsung also makes the SSD for the MacBook Air so the swap shouldn't be that hard to do. If you wanted to save some money you could opt for a 32GB SSD, which will be considerably cheaper. Another alternative is to wait for 64GB SSD prices to drop and simply upgrade later.