High intensity interval training is a great way to improve your overall conditioning and stamina.
I usually run 3-4 times a week for about an hour in the morning, not to increase my stamina, just cause I enjoy it. When I wanted a great cardio workout I started doing interval sprints.
In a park near my house I marked out a 100 yard distance. Then I sprint, balls out the whole way, and jog back to the beginning(I walked back at first). I then repeat this a total of 10 times. By the end, my heart and lungs are on fire, and my legs are wiped.
After doing this once a week for a few months along with my usual running, my cardio shot through the roof. My hour runs used to be tough, now they barely put a dent in me.
Regardless of what you are doing, whether it's running, biking, swimming, whatever, make your sessions high intensity, and you will see results fast.