-Better pads (Scott/Matthauser, Ritchey, Kool Stops)
-Brake brace
-Properly adjusted brakes.  Make sure you have some toe-in and your pads 
 are hitting the rims straight on.
-Scrub the rims with alcohol to remove brake "bake-on".
-Sand the pads to remove glaze
-Get new and better brakes/levers

To this, others added:
Charles Coker [CHARLESC@hhsc.state.tx.us] and
Peter Greaves [greaves@ccmail.ram.co.uk] suggested that:
-Lower the straddle cable to about 3/4's of an inch above the tire.   

John Stevenson [johnstev@world.net]
On current Shimano brakes (that is, ones with a link wire) the most common
brake set-up error I see is that riders replace their blocks, pushing the
stud all the way into the clamp on the cantilever body, then pull the cable
through so that the brake works. Problem is, this leaves the link wire and
brake cable pointing skyward at a very acute angle, an arrangement which
results in very low mechanical advantage at the brake, in other words lousy
braking; a very 'hard' feel at the lever with very little braking power
unless you really haul on the brakes.

These Shimano brakes should be set up so that the cable and link wire form
at least a 90 degree angle. More will increase braking power still further,
but at the expense of a spongy feel and need to set the blocks very close
to the rim.

[note from the author]
To get the best angle with the straddle wire, whether it is the conventional 
straddle wires or Shimano's hangers, you can use the older generation of the 
Shimano Pro-set tool.  It holds the brakes together while you tighten the 
nuts/bolts.  This works because the older style cantilever brakes are much
less upright and require a greater angle in the straddle wire.

Ming Dong [ming_dong@netgate.net]
Brake boosters help by preventing brake boss (mounting stud) movement.
If you have powerful brakes on a soft frame (Ti), they will move 
alot. If you have weak brakes on a heavy steel frame, you probably
won't notice a difference. 
  
To check your frame for brake boss flex, hold the brake bosses between 
you thumb and index finger and apply the brakes (with your other hand
dummy:-) Did the bosses move much? If not, maybe you first need to
optimize your brake adjustments and replace frayed or kinked cables.
In other words, a brake booster is the last thing to add, only after
you've checked eveything else.  It's not a panacea for poor brake
adjustment.