I am also not Donald X., but here is a much longer description than liopoil's about what happens, intended to help you understand why these things happen as they do. If something is confusing here, please ask about it and I or somebody else will try to clarify.
You follow the wording on the card exactly as it is written. Procession says:
You may play an Action card from your hand twice. Trash it. Gain an action card costing exactly $1 more than it.
So after you play Procession, you choose a card to play. You play it twice. Only after you've played it twice does Procession trash it. However, it is possible that the card will cause itself to be trashed. After Procession tries to trash it, you gain a card costing exactly $1 more than it.
The timing on all Dominion cards is exactly as written on the cards. If something happens at a different time, it will say so (e.g. Scheme specifically talks about the start of the clean-up phase). Just follow the instructions exactly as written on the card.
So with your specific example of Death Cart...
First you play Village.
Then you play Procession.
You choose Death Cart.
First play of Death Cart: You get +$5, then you can choose to trash an Action card from your hand. If you do not, Death Cart trashes itself.
Second play of Death Cart (note: it gets played a second time even if it already got trashed): You get another +$5, and you can choose to trash an Action card from your hand. If you do not, Death Cart trashes itself.
Up to this point, the way Procession works is the same as Throne Room. If you play TR+DC, you'll have to trash two Action cards from your hand or else Death Cart will trash itself.
But now, after you've played it twice, Procession tells you to trash the card you choose. If Death Cart was already trashed, you can't trash it again. If you did trash two Action cards from your hand when resolving the two plays of Death Cart, then you still have to trash Death Cart now due to Procession.
After you've trashed it, then you gain an action card costing exactly $1 more than it. Most of the time this means that you will gain a $5 action card (exceptions: no $5 action card available in the Supply; cost reduction via Highway, Bridge or Quarry changing the cost of Death Cart and other cards on the board). For example, you might gain a Graverobber. The gained card goes into your discard pile. Note that this instruction to gain a card does not say "if you do" at the start, so it happens even if Procession fails to trash the chosen card in the previous step. Procession maybe did not trash Death Cart (because it already trashed itself earlier) but you still gain an action card from Procession.
Only now are you done resolving Procession. Since you played a Village, you still have 1 action remaining (the plays of Death Cart were part of resolving Procession and thus did not take up extra actions). If you have another action card in your hand, you can play it now. You could play a Graverobber in your hand to retrieve the Death Cart from the trash, putting it into your discard pile on top of your deck and gaining two more Ruins, which go into your discard. (You could even play, say, a Laboratory, triggering a reshuffle and drawing the Graverobber you had just gained from Procession and then play that Graverobber...)
So to answer your questions directly:
- Procession trashes the chosen card during its resolution -- after the card is played twice, before you gain a card.
- You can use Graverobber after Procession to gain the card back, providing that you have an action to play Graverobber from your hand, and that the Procession'd card is in the trash (which might not be the case with some cards such as Island or Fortress).
- If the Procession'd card gets removes itself on the first play (e.g. Death Cart trashing itself, Island islanding itself), you still get to play it the second time.
Edit: correcting Graverobber stuff, as per AJD's post below.