At my airline, fuel optimization has been a huge issue over the last few years as fuel prices have skyrocketed. We do things quite a bit differently from Dave's airline. Here, the Captains order fuel for themselves with little input from dispatch, with the request that they try to save the company money when possible. There are some captains who always just take min total plus a few hundred pounds, but most are pretty good about working out the optimal fuel load.
There's a large disparity between fuel prices at our hub cities and those at most outstations, so it almost always makes sense to tanker fuel on outbound legs. This is much more of a no-brainer on the Megawhacker than most jets, because unlike jets, the extra weight does not result in appreciably more fuel burn. The most common explanation I hear is that jets fly a given mach number and increased weight requires more engine power to maintain that mach, whereas we just set cruise power and accept whatever airspeed we get (or pull the power back to stay under Vmo). I think there's more to it than that, because you'd think that all other things being equal, increased weight results in decreased airspeed and higher fuel burn for the leg. I think the real difference is that most jets are flying close to their maximum altitude, where extra weight increases induced drag appreciably. The Megawhacker always flies far below its aerodynamic maximum altitude (it's restricted to FL250 by lack of O2 masks and the pressurization differential limit); our angle of attack is only a degree or so in cruise, so extra weight doesn't increase induced drag much.
Whatever the explanation, it always makes sense to tanker when we're flying somewhere that fuel is more expensive, so we simply figure out how much we can get away with taking. Maximum takeoff weight (MTOW) on the Megawhacker is 65,200 lbs, and maximum zero fuel weight (MZFW) is 58,000 lbs, so you'd think that we'd always be safe taking 7400 lbs (7200+200 lbs taxi fuel). However, many of our shorter legs are weight limited not by MTOW but by the Maximum Landing Weight of 62,000 lbs. If this is the case, you add the expected fuel burn to 62,000, and that gives you your new max takeoff weight. You subtract MZFW of 58,000 from that, and this gives you the most fuel you can take while protecting max payload. If this number is below min total and you have a full boat, you may need to bump bags or pax.
This method protects maximum payload by assuming you'll be at MZFW, but that's seldom the case with the Megawhacker. Even with 76 passengers, it's rare to have so many bags that we bump up against MZFW. Every pound below MZFW is a pound of fuel we could be tankering. The trick is to guess how much payload we're going to have before boarding, when we write the fuel slip. To that end, the company has begun providing load planning sheets, printed 25 minutes before departure, which estimate passenger load and cargo weight. Most captains leave a little wiggle room for last minute passengers and jumpseaters. You add the expected payload to aircraft Basic Operating Weight (BOW), subtract that from most limiting takeoff weight, and that gives you fuel load. When passenger loads are light, we might fuel all the way up to our maximum capacity of 11,700 lbs.
It is, however, possible to tanker too much fuel. You need to take the next leg into consideration. If you're doing a short turn (SEA-GEG-SEA for example), you don't want to put so much fuel on that you arrive back in the hub city with 4000 extra pounds of fuel! Worse, if you have a lot of payload on your next leg, you could find yourself with way too much fuel and be forced to bump a lot of people or bags. Our dispatch release tells us how many people we can expect on the next leg, and the more conscientious dispatchers put down the expected min total fuel as well. The ideal is to tanker enough fuel to arrive with more than min total, but not so much that you risk bumping payload.
It seems like a complicated process, but you get pretty good at it after a few weeks on the line, to the point you just "know" what to tanker by looking at your release and load planner. The company recently added a fuel optimizer program to the PDAs they issue to Captains, but it turns out that the program doesn't work nearly as well as the old method. The really effective way to do this would be to just take the pilots out of the picture like Dave's airline does; let the airline decide when to tanker. That way, the only decision the Captain needs to make is whether the company's number gives him/her warm & fuzzies, and if it doesn't, exercise their prerogative to add some extra.