While I like using Mail.app with Gmail I don't like the 'All Mail' folder. Here's how to configure Mail so a deleted message ends up in the Trash folder on the Gmail server.
In Mail.app, under Preferences click the Accounts icon. Select your Gmail account. In the Trash section check the box 'Move deleted messages to the Trash mailbox' and check the box 'Store deleted messages on the server'. Close the Mail.app Preferences.
On the left side where the Mailboxes are located, expand the Gmail folder, and click on the Trash folder. Next, from the Mail.app menu select Mailbox » Use this Mailbox For » Trash.
Now messages you delete in Mail.app will from now on be moved to the Trash folder where you can permanently delete them by selecting them and pressing the Delete button on your keyboard or by enabling the automatically delete after x number days setting in Mail.app preferences.
I hope you find this hint useful. It's tested on Mac OS 10.7.2 Mail 5.1.
[crarko adds: It looks to me that these options are available in 10.6.8 Mail as well, although I haven't verified that it works the same.]

