When you press `d' in the index or pager views to delete a message mutt will flag it with a `D' in the index view (it may also reflect the deletion using color: my mutt is configured to show deleted messages in red. We'll look at the options available to you in sec. 4.2) - but doesn't actually delete the message until you either change to a new folder or sync the mailbox to commit the changes. To make the deletion permanent, press the $ key, which is the default command to sync the index with the server and actually deletes all messages flagged for deletion. Up until that moment, you still have the option to undelete those messages.
Undelete a message by putting the cursor over the desired message and pressing the `u' key. You can navigate there either by using the message number, or by holding down shift as you type `J' and `K.' Otherwise, the cursor will cavalierly jump right over all deleted messages as you navigate.