It sounds like you're using Gmail, in which case, have you checked the All Mail folder? Gmail treats things a little differently, and I believe the default action for "delete" when using Mail.app with Gmail is actually what Google calls "archive".
It doesn't delete it from the server, it just removes it from all folders (labels in Gmail-speak), but the message still lives in the All Mail folder.Check there for your messages, and you may find this previous answer helpful: Set up Gmail to work properly with Apple Mail
If you're not using Gmail, or that didn't work, try this:
- In Mail, open the Preferences (⌘ command-,)
In the Preferences window, click the Accounts panel and select the applicable account in the sidebar as shown here:
Select the Mailbox Behaviours tab
- Make sure the Move deleted messages to the Trash Mailbox setting is checked:
If it's already checked, make sure your Trash is set up properly, by selecting the mailbox you want in the main sidebar, then goto the Mailbox Menu, and choose Use This Mailbox For ‣ Trash.
That should fix it. If not, your problem may be on the mail server, or something more obscure locally.