The way to increase you lung capacity (vo2 max) is to perform interval training and sprinting, one technique is known as Fartleks. The more you push your lungs (and get out of breath for short periods), the greater your capacity becomes, at least up to a point.
One interesting device that is a fairly cheap that claims to improve your inspiratory muscles is the Powerbreathe. It works by you blowing into the device, and it providing resistance for both. Like push ups or press ups, you increase the amount you do each day, and also increase the resistance.
It has various studies to back it up but from experience is a bit of a pain to clean - you have to buy baby milk bottle sterializer to clean them with.