An exhausted character moves at half speed. If a character has a speed of 30 feet he moves at 15 when exhausted. Can he run or charge when exhausted or is he also fatigued? Is an exhausted character always also fatigued?
A creature can become exhausted without first becoming fatigued (e.g. a creature affected by the spell waves of exhaustion).
The Rules Compendium updates the condition exhausted to say
An exhausted creature can neither run nor charge, and it takes a –6 penalty to Strength and Dexterity. It can move at only half speed. After 1 hour of complete rest, an exhausted creature becomes fatigued. (35)
A fatigued creature can neither run nor charge and takes a –2 penalty to Strength and Dexterity. Doing anything that would normally cause fatigue causes a fatigued creature to become exhausted. After 8 hours of complete rest, a fatigued creature is no longer fatigued. (35)
Thus a creature that's somehow both exhausted and fatigued, in addition to other effects, suffers a –8 penalty to Strength and Dexterity as the ability score penalties are from different sources.
However, this DM recommends against actually playing these conditions as conditions that can be uniquely gained, and, instead, recommends treating the condition exhausted as a more severe form of the condition fatigued, especially considering that the effects of the condition fatigued were fully subsumed into the effects of exhausted with the Rules Compendium's definition.
Consequences of playing this way anyway
After 1 hour of rest, a fatigued and exhausted creature's exhausted condition becomes the fatigued condition and combines with the already-possessed fatigued condition to make the creature exhausted again therefore requiring the creature to rest another hour to decrease the exhausted condition to fatigued. This is complicated but not dumb.
The dumb happens when a fatigued and exhausted creature becomes fatigued again then becomes only exhausted, a creature being unable to be exhausted twice. But, as the game includes such quirks as healing folks by drowning them and fire resistance 1 allowing painless, limitless lava-swimming, this, by comparison, shouldn't be that big of a deal.
The really dumb happens when, as Ilmari Karonen's Comment mentioned, an exhausted creature takes an hour's rest in an effort to end the condition exhausted and gains the condition fatigued, but—according to this beautiful highly technical, really hardcore rules-as-written reading—doesn't lose the condition exhausted, making it so a creature with the exhausted condition makes things noticeably worse by resting and making it so that, essentially, the exhausted condition can't be removed except by magic.
This last is probably the clearest indicator that the condition fatigued should be subsumed into the condition exhausted when the condition exhausted is gained, the designers having merely accidentally omitted the line of text saying so. Incidentally, this is also why there are DMs: to adjudicate oversights just like this one.
In short: No they don't stack, Yes an exhausted character counts as fatigued.
Exhausted is a more dire version of fatigued. Unless a fatiguing effect explicitly says so, if it were to fatigue a character that's already fatigued, that person will instead become exhausted. If you recover from Exhaustion naturally, your condition will improve to Fatigue.
While you can't run or charge while Exhausted, you would be calculating your move based on half your speed if you found away around that.
An exhausted character moves at half speed and takes a -6 penalty to Strength and Dexterity. After 1 hour of complete rest, an exhausted character becomes fatigued. A fatigued character becomes exhausted by doing something else that would normally cause fatigue.
A fatigued character can neither run nor charge and takes a -2 penalty to Strength and Dexterity. Doing anything that would normally cause fatigue causes the fatigued character to become exhausted. After 8 hours of complete rest, fatigued characters are no longer fatigued.