Well then the answer is simple, the best case solution is a switch mode 5 volt to 3.3volt regulator. It will not waste 5 volt power just to turn it into heat, so the total wattage consumed from the 5 volt bus from any given 3.3 volt load will be less. Next question?
I don't think that's the best solution either, as somewhere in the chain you have a
5V v.reg that's dissipating a huge amount of heat. Better to run the 3.3V dc-dc
converter off Vin in the first place. No?
And after all, a 3.3V "linear" v.reg running off of 5V really isn't gonna be generating a
lot of heat anyways. Eg, (5V - 3.3V) * 0.5A = 0.85W, whereas the 5V linear v.reg will
be dissipating much more, just to power the 3.3V device. Eg, (9V - 5V) * 0.5A = 2W,
not to mention any other loads.
So you see, OP, there are probably no universally agreed upon solutions to much of
anything.
Actually, a solution I like a lot is being using by Pololu on their Zumo shield. They use
4 rechargeable AA-cells to power a 1 Amp dc-dc converter that puts out 7.45V.
Then you can connect your Arduino board to that. Even if it's using linear v.regs,
they're not running super hot [except maybe for those tiny SOT-223 parts that I
dislike - I always use TO-220 or DPAKs myself].
http://www.pololu.com/catalog/product/2504[Edit after the fact: after reading through some of the other posts, and in light of
what I said here above, I like the Due idea of a dc-dc converter for 5V powering
a linear v.reg for 3.3V. Good compromise].