GPS will give you altitude data. There's at least two GPS shields for Arduino.
One from Adafruit: Adafruit GPS logger shield kit [v1.1] : ID 98 : $19.50 : Adafruit Industries, Unique & fun DIY electronics and kits
One from Sparkfun: SparkFun GPS Logger Shield - GPS-13750 - SparkFun Electronics
(note that neither shield actually includes a GPS module!)
Most GPS receivers communicate via 4800bps async serial (compatible with the serial port on the arduino), so it is "relatively easy" to interface many gps receivers to arduino... I read somewhere that most of the cheap ($25-40) USB GPS modules you can buy on eBay include a serial port internally and use a USB/Serial converter (like the one on arduino), so connecting to an arduino only requires bypassing the GPS USB converter...