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.
I created a simple Mail.app plugin that you can install to restore the pre-Maverick archiving behaviour. You can find all the details on my website:
For returning to the pre 10.9 behavior, see http://steve.blogs.loeppky.com/2013/12/mavericks-apple-mail-with-gmail-getting.html .
For archiving with the delete key, see http://akgungor.com/2013/11/11/delete2archive-archive-gmail-messages-using-delete-key-os-x-mavericks-mail/