Mail.app in Mavericks moves Gmail mails to Trash instead of Archiving them
Solution 1:
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.
Solution 2:
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:
Delete2Archive - Archive Gmail Messages Using the Delete Key in OS X Mavericks Mail