Both at the same time.
I doubt anyone is going to argue that losing weight and/or becoming more physically fit is not going to help you on the trail.
Why think of it as one before the other?
When taking on any physical activity isn't it about making sure that you have the right gear to keep you safe and comfortable, as well as making sure that you are physically up to the challenge to complete it safely?
For me, skinny dude that I am, going lighter has allowed me to take on longer and more difficult trips....however, I worked my way up to those longer trips by taking the shorter ones to get experience with my skills and to provide myself with some conditioning.
Maybe we can look at it in terms of going lighter might help motivate or make it possible to just get out there vs. carrying a traditional 35-50 lb load for a weekend, which in turn helps someone get into shape and lose some weight?
So my answer is do both at the same time.
Exercise by itself sucks....I have a Stairmaster and a full weight machine, which make great clothing hangers for airing out my clothing & sleeping bag after a trip. :)
As my friend, Jeremy, has told me, "The only way to train for climbing mountains is to climb mountains".