There is a several hundred word long tutorial,
Full Step-by-Step Tutorial taken from here, that I have used to solve this problem so in addition to the author testing it, I too have things fully working.
Here are the steps from the article as well as details from the two key steps.
Step 1: Configure Apple Mail preferences
Step 2: Assign mailbox functions
Step 3: Set the [Gmail]/ prefix on custom labels
Step 4: Designate which labels show in IMAP
Since this is the most important step, here are the details
While you’re in the Labels tab, uncheck the “Show in IMAP” box for All
Mail because you don’t want that showing up in Apple Mail anymore.
This is important to ensure the delete button sends messages to the
Trash in Mail.app. The “Show in IMAP” box will determine which labels
appear in Apple Mail. Feel free to uncheck the “Show in IMAP” box for
any other labels while you’re at it. Changes are saved automatically.
Step 5: Forwarding and POP/IMAP
This also is a key step where google allows you to delete a message once it's removed from tha “last visible IMAP folder.” By hiding the All Mail label in IMAP, there should only be one “visible” copy of your message, so when you delete the message in Mail, it will now move the message to the Trash.
Step 6: Restart Apple Mail
Step 7: Test it out
I've tested this on Lion 10.7.5 and works perfectly.
All images are from Jeff Schuette as is the quoted text explaining how google can be set up to work like all the rest of the Mail servers to delete messages when you trash them.