Mail.app in Mavericks moves Gmail mails to Trash instead of Archiving them In OS X before Mavericks, Mail.app with a Gmail account would remove messages only from the inbox when deleting them,  but leave them in the All Mail folder; essentially archiving them. In Mavericks it now moves them to the Trash entirely. What gives?
Mavericks Mail.app is now actually aware of the All Mail folder and has "archiving" as a separate concept, just like iOS does. The old delete-from-inbox-to-archive was arguably a hack in Gmail's IMAP implementation which now no longer works. Now "Delete" actually means delete and "Archive" means archive.

The new command is in the menu under Message > Archive, its keyboard shortcut is ⌃⌘A. You can add the Archive button to the toolbar via View > Customise Toolbar... if it's not there.

Apparently you will also have to show the All Mail folder to IMAP clients, which is something you have to configure in your settings on the Gmail website. I have not confirmed this though, I always had it on anyway.