Disclaimer, like Bernarr stated in his post, the sensitive need not listen:
Sir Ulrich, as Bernarr has alluded to, hiking isn't going to cut it if you're serious about building fighting stamina. Real fighting can be sustained all-out physical exertion, which will completely exhaust you in less than a minute if you're not in good condition. Running isn't even really enough. You really need to get serious about physical training if you want to be in good 'fighting shape.' All the programs he mentioned are very good. I've done both P90X and Insanity myself. Insanity will definitely get you in the proper physical condition if you stick with it and complete the entire thing and give it every ounce of will power you've got. If you don't, you can expect minimal results.
You have to bear in mind that the men who did this for real, i.e. real knights and men-at-arms, did this literally for life and death. You had to have every edge up on your opponent if you wanted to live. Fighting without a harness on is exhausting, these men did it with an extra 50-80lbs of steel on, limited visibility, and poor ventilation.
You don't need to do a specific exercise program, like P90X or Insanity etc, but they will help you because they're so structured. The other good part about them is you can start at your current fitness level. What you really need to do is a combination of intense resistance training in the form of weight lifting, and intense cardio, generally in the form of high-intensity interval training to really build stamina. If you jump in and try to go all out at the beginning, you will injure yourself or not make any progress and get discouraged and stop. And look, no offense, but any weight lifting you did in the past, all those strength gains you may have made, despite what you weigh now, it's all GONE. It doesn't stay with you if you're body doesn't need it anymore, it's just how our body's work. As soon as you stop lifting, all that extra muscle mass that your body doesn't need anymore slowly catabolizes and fuels your body and the weight you have now, whether it's visible or not, is not muscle mass, it's fat.
Fitness is really a lifestyle, it's not something you do casually. If you're interested in really learning to be in good shape, I will help you get started. Fitness is an important part of my life, and I take it very seriously.
EDIT: Look at the Battle of the Nations Polish training video Thorsteinn posted in the other thread and observe the athletes during their warm-up at the beginning. You can see just by looking at their physical condition that these guys take their physical training seriously, not a fat, or weak out of shape person in the group.