Nitrites hamper a fish's ability to process oxygen. That's why your fish are gasping.
As everyone has said, water change. The air stone will help the fish for the time being, but the only way to really help them is to get the nitrites down to 0.
Once your tank is cycled, you won't need the air stone.
Roan