Play by mail mechanics vary immensely, to the point where there are probably as many possibilities for rules in PBEMs as there are in tabletop pen and paper RPGs. Some games use pen and paper rules sets, some use board games, others custom PBEM rules (or programs) and some no (mechanics) rules at all.
What I have found from my experiences in both playing and running PBEMs is that there are three general "styles" of PBEM that dictate how rules, resolution and interaction are handled between players and the game environment.
One important, immediate thing to realise is that in PBEMs, personal (small unit) tactical combat using dice resolution for every action is generally very, very rare. It's slow, tedious and annoying to (for example) try and run a D&D 3.5 combat through email; it is not what this type of game is about.
That said, I'll break down your questions for each game style.
1. Tactical PBEM
A tactical PBEM consists of a game where players submit a series of orders (usually on a simultaneous deadline, but they can be on a round-robin basis as well). The GM then makes any rolls/checks/etc. required to determine the outcome and sends out results to the player(s) involved. These games tend towards more tactical and management styles of games.
Email replies for this style of game are usually personal and contain information that would be "of use to the enemy."
How is this style actually played?
Players submit a series of orders. Such as "Move unit 6 north six miles, engage any enemies" or "Week one attempt to join the East Anglian Regiment, Week two if I am in a regiment train, if not carouse."
How should players describe their action, in a way that does not mess with the story?
Story in these games tends to happen in part by resolution from the GM, but also between turns via public forum, email, etc. among the players in a way that will not contradict order results; i.e., players provide as much fluff as they want (and it can be a lot). The golden rule for this style of game is "don't interact in a way that will contract any possible actions." – You can't say, "I'm in the Anglian regiment now," if your order to join it hasn't been resolved either way yet.
How is an action resolved?
The GM will resolve all orders for this style of game, sometimes using a program to manage the orders automatically and spit out the results sheets.
Importantly, how does someone GM something like this?
This is a reasonably easy type of PBEM to manage mechanically as all orders are well defined and interactions have black and white results (as long as the rules set holds up!). As mentioned there are even programs to do this, to the point where the GM can just collect the orders and stuff them into a program to resolve it all for them. Manual mechanical systems however can take a lot of time for a GM to resolve.
What examples are there of this?
En-Garde, Diplomacy, It's A Crime. There was even a version of UFO: Enemy Unknown that ran via email. Stars is an example of a program-run PBEM.
Note that although these games are generally tactical/management heavy they can generate a lot of fluff. Message boards and email lists are usually set up for this sort of game where players can interact, describe events, tell stories about their realm/character/corporation, make threats, etc., entirely irrespective of the actual game turns – and as results arrive they can react to them.
2. Narrative driven PBEM
These sorts of PBEM usually have no mechanics rules at all and typically focus on a single character per player. They are virtually interactive/freeform stories. The game rules generally boil down to three crucial laws for the game world.
- Stick to the setting's genre and theme.
- You cannot affect any other characters or important elements without their players' permission (or the GM's, for non-players). (See below.)
- Wheaton's Law.
These games are story based games and entirely fluff driven; players in the game write stories about their characters in the setting provided and managed by the GM. The players typically have control only of their own character. Where two characters interact, players either communicate directly via email to determine resolution and agree on something or try to predict the responses from the other player and leave placeholders in their stories so that the other players can respond from their character, subject to law #2.
Email replies in this game are usually to an open forum or mailing list so everyone can follow what is going on. Character sheets for this style of game may have no mechanics or statistics at all on them (and indeed usually don't), just description and background.
How is this style actually played?
Players write stories and describe what their characters are doing. Enjoyment comes from crafting a well written saga rather than slaying 200 billion orcs. Usual focus is on character development. An example slice might be:
Trendar looked out over the shattered remains of the town and shook
his head sadly, they had been too late, the enemy had destroyed their
home and everyone they knew. He looked to his friend and companion,
Eric the Grey.
"What do we do now? There's no-one left, we're lost, this is the end."
[[tag for Eric to respond]]
"You're right, they can't get away with this."
The stories and replies are usually somewhat more expanded than this! Note that the GM may not even interact with players once they get going and this can be ideal; two (or more) characters follow off on a thread together on an epic quest and create a story together.
How should players describe their action, in a way that does not mess with the story?
This is the trickiest element of this style of game; it involves either predicting how someone will react or communicating personally with them and determining what will happen. The GM controls the world and the NPCs (although players can help) and will guide events (through descriptive messages).
How is an action resolved?
By agreement. Players in this style of game must be flexible and willing to make an interesting story and not want to "win" all the time; indeed winning becomes exceedingly boring in these games. The trials, failures and struggles that lead to character development are what is important. When characters "fight" then they both need to be willing to give/lose something in such an activity or they are not going to have fun – and more importantly no-one is going to what to play with you if you always kill your enemies. Death is not a common character occurrence at all. Think soap opera.
Importantly, how does someone GM something like this?
GMs provide the flavour, the big events, the big bads; they are like a director in a movie that provides details of the approaching army, the details of the plague that is sweeping the land, the earthquakes that shake the city. They also manage important NPCs. This can be a lot of work, but they also get to write a lot of story. The hardest thing for GMs is managing players who do not understand that this sort of game is a cooperative effort rather than a personal ego trip; such players need to shape up or ship out.
What examples are there of this?
Absolutely anything can be made; existing book/film/game genres are very common choices (Mass Effect, Star Trek, Conan the Barbarian, etc.) so that new players are aware of the setting. It can be a GM-made world of course, but this requires a lot more reading for the player and tend to be harder to get started in. Star Trek PBEMs in this genre are one of the most common.
Games of this style can end up being very much like play by post games (i.e., forum games) but at a slower speed. i.e., instead of determining what happens via email or trying to guess a response, the players simply stop the story and tag the character (or GM) they're interacting with to continue the story.
3. Downtime PBEM
This sort of game is usually an in-betweener or more a "high level" facet of an another ongoing campaign. An established rule system is used (AD&D, Rolemaster, whatever) and the players describe what they want to do. Combat can occur, but it is usually avoided as the players in this are looking for more management and personal interaction.
Email replies for this sort of game are typically personal, but aspects of what is happening are usually broadcast around on a mailing list. e.g., "All hail! the King declares that the grand Sir Eric has been made a Knight of the Order of the Rose." And so on.
How is this style actually played?
This style is the most varied, since it can be as little as a means to keep a tabletop game going while players are away. Typically players will describe what they want to get up to (in varying amounts of detail, from simple one liners to many paragraphs) and then the GM replies with what's going on.
How should players describe their action, in a way that does not mess with the story?
This is a "what you put in is what you get out" style of game; players who use short descriptions and don't like story will find this boring. The GM will sometimes have to reign in players who make assumptions about what happens and have their characters try to do too much.
How is an action resolved?
Action is resolved using the game system used in the main game; combat can be tricky but this is usually resolved either in a short real-time online session between the player and GM or with a few rolls by the GM.
Importantly, how does someone GM something like this?
This depends a lot on how much the players put into the game; the rules system is your bible and constraint for managing the players. Events can continue but the important thing is to avoid combat as much as possible so that character development can continue. In the end it's a lot like a tabletop session, but with the focus on development rather than hitting stuff.
What examples are there of this?
Almost any pen and paper RPG can be adapted for this. Some are more suitable than others; generally games that focus on the tactical aspects of a character's ability (such as D&D 4e) are less suitable than ones that describe a character's persona and abilities (such as Fate).
TLDR
PBEMs vary immensely. There are three general styles: Tactical, Narrative, and Downtime. Combat is a rare affair in the latter two, which generally concentrate on fluff. Tactical games tend to focus on larger-scale management and combat between units.