Decrease pack weight!
As far as exercise, from someone who has had knee pain since the age of 19 and tried every exercise, bodywork, you name it:
Walking is the best, period. Running up hills or up stairs makes you stronger still, especially in the ass (a strong ass is very helpful on the downhill), but only if you're strong enough.
I've reinjured and aggravated my knees countless times trying various gym exercises - squats, lunges, step-ups, etc. Some of those movements are OK, biomechanically, but done repetitiously I think they take more than they give. We evolved to pick up heavy things (squat, deadlift), to make demanding agility movements over variable terrain (lunge, step-ups), sure. But we especially evolved whilst walking and running.
I like to walk until my legs feel springy and I spontaneously have the urge to run. Then I sprint at 80%, but only ever uphill. The feeling I have is that running uphill is like a series of one-legged jumps where I don't really land, and thus don't really have a heavy impact - it's just one jump followed quickly by another, continuously going up, up, and never really thumping down. I used to like to run up a five story building and then take the elevator down to save on the downhill pounding.
When hiking downhill I almost never run, although sometimes I'll go quickly, taking very short steps toe-to-heel, like dancing.
Hiking barefoot or in very simple shoes from time to time or as a habit helps tremendously. Counterintuitively, barefoot reduces impact as you use your entire kinetic chain to reduce impact on the foot, which leads to a looser, liquid gait. A study done a couple of years ago showed reduced loads at the knee, hip and spine when knee osteoarthritis subjects walked barefoot as compared to with their shoes. Agrees with my experience.