For a long time the default and very painful behaviour between the integration of iOS devices (iPhone/iPad) and Gmail’s Exchange support (required for push email) has been that whenever you delete an email it will actually archive it instead (put it in the “All Mail” folder).
Like me many people hated that and have been complaining for a long time on Google’s Forum, Groups and Feedback sites. I have personally been using a “delete” label and moving messages there to delete later on my PC.
Apparently Google have quietly (I have not seen an announcement?) added a feature to disable this annoying behavior and deleted mail will end up in Gmail’s Trash folder instead.
To enable it you have to open the Google Sync settings page from your mobile device at http://m.google.com/sync . Note that you can not access this page from your computer.
In there you will see a new checkbox saying something like “Move delete mail to Trash”. Tick, save, boom.
P.S: BTW for those of you who don’t know this is also the place where you pick which Google Calendar Calendars to make available for syncing on your device.