This is a classic physio exercise. Barefoot, CLOSE YOUR EYES and lift one foot off the floor (just a little) and stay there for as long as you can. You'll fatigue faster than you think at first. Strengthens the little muscles that stabilize the foot and ankle. This is easier in shoes as the foot is somewhat stable. Once you're not too wobbly and won't risk embarrassment, you can do it in line at the bank.
Here's another one. Walk backward on a tread mill at about a 7 degree incline at maybe 2mph. You want to take large controlled steps on this one and really feel the knee tracking.
I have one I like related to Paul's post. I like it for ski season — I run down hills (I think this is an exercise for smooth pavement) slaloming, varying my turn radius down to zipperline bumps. Trying to angulate a bit.
I never carry a load unless I have to — basically once I set out on a long hike. I never use sticks unless I have a significant load. Without a load, I usually walk way too fast for my sticks to keep up anyway.
Core stabilization but NEVER crunching movements. http://well.blogs.nytimes.com/2009/06/17/core-myths/?scp=1&sq=ab%20exercises%20back&st=cse Try the stirring the pot in the video.
As many different activities as you can. When it comes to walking trips, just walk myself into shape over the first few days.
And I am woefully inconsistent with all this. :)
SHORTEN YOUR STRIDE! This is much more efficient. You will move much faster. And in the event of a slip, you are much less likely to injure yourself. Once I put on my pack, I am extremely conscious of stride length.
DON'T TRAIN. DO PLAY!