Fitness is very important IMHO if you want to increase your mileage in combination with enjoyment out backpacking. There is a point where cutting weight only goes so far!
I've been doing a bit of reading lately (sorry I haven't kept references) on strength training for endurance athletes, particularly with how relative number of reps and weight contribute to different aspects, etc.
Its important to note that maximal strength, as well as power, power-endurance and strength-endurance are all important facets that lead to increases in performance in endurance athletes. Body weight is also important; a heavier athlete with the same strength as a lighter athlete will usually perform worst.
Thus, lately I've been concerting my reps to hit those ranges based on what I've read in peer-reviewed literature and the vast array of "expert" dialogues (eg Magazine articles based on a trainer's experience/perception). I also mix things up; I don't have a set routine, I try to keep the body guessing, and periodise somewhat, even if its periodisation within a week. I try and avoid rep ranges that are more proven to lead to hypertrophy (generally the middle ground around the 6-15 range) as I don't want to put on any superfluous bodyweight. Sets with reps 1-5 generally promote focus gains in maximal strength, while 20-30 are deemed pretty good for strength endurance. Beyond 30 I don't personally see a huge point unless its a bodyweight exercise (eg pushups, full body dips, chinups) or a more functional sport specific exercise (eg say doing 100 walking lunges with a very heavy rucksack) or one that is more targeted at facets of aerobic endurance (eg rowing).
My current rough period is mainly focused on strength and strength endurance (Note that I also do a lot of cardio work outside the gym, and I'll hit a new period where I'll include more power and power endurance in a month or two). I often warm up with sets of 20-30, aiming to hit a set of 20, then move the weight to what I can handle for ~5, then increase it gradually down to ~1 or 2. I don't worry too much about how many sets or total reps I do, as long as I feel that I am pushing myself to a certain level. I often complete a final set back in the endurace (20-30) rep range. I'm concentrating mostly at the moment on upper body as my upperbody strength is rather pathetic, and though I am an advocate of full body Olympic and Power moves, I'm so out of balance bottom to top I'm struggling; last night I did some deadlifts after a warm-up, hitting only 60kg for 5 reps before my upper body really couldn't handle any more weight with good safe form. My legs didn't even feel it...about three years ago I could deadlift 135kg for three reps (body weight 83kg)...I reckon my legs could handle 180kg+ easily now (bodyweight 78kg), but I have to build my upper body strength first to handle more than 60kg. The result of too much cycling!
Note, my personal results are rather pathetic!
Note also, that my personal fitness goals aren't totally related to fastpacking, though they are somewhat. Having a strong upperbody only goes so far in helping if you are only ever carrying an ultralight pack. However it is important. If you disagree, start reading and following Mark Twight!