I've figured it out. I can't say there's really one clear method listed elsewhere, I just kinda pieced it together. Here is the solution, as clearly as I see it. This is how you can permanently delete Gmail messages using Apple Mail. I'm using Mail 5.0 on Lion 10.7, but this probably works for 4.x/10.6.
You should have already enabled IMAP in Gmail via Mail Settings > Forwarding and POP/IMAP > IMAP Access. Auto-Expunge should be ON by default. Don't forget to "Save Changes" if you've adjusted anything.
In Apple Mail, under Mail > Preferences > Accounts > Mailbox Behaviors, make sure that both options are checked "On" for Trash. (Move deleted messages to the Trash mailbox; and Store deleted messages on the server.) The option to "Permanently erase deleted messages when:" can be set to whatever duration you wish, but I'm using "One day old" to give me a few hours to change my mind if I need to fetch a message back from the dead.
Next, in Apple Mail, you will need to "Show" the sidebar that lists accounts and folders if it's not visible already. Find the Gmail account, and look in the [Gmail] folder. Select the Trash folder, then choose in the top menu Mailbox > Use This Mailbox For > Trash. (While doing that, you might also want to choose to map the other folders Drafts -> Drafts, Sent Mail -> Sent, and Spam -> Junk, although none of those really has anything to do with this issue of permanently deleting mail.)
Now, here's what happens with the above settings:
When you are viewing an email in the inbox and choose to delete it, hit the delete key, as you would expect. Normally this would result in the message being removed from the Gmail inbox but remaining in the Gmail All Mail folder (aka label). But with the above settings, the message is also removed from All Mail, and goes straight to the Gmail Trash folder. At this point, the message will disappear either automatically (eventually, depending on your duration set above to "permanently erase deleted messages"), or you can immediately *manually* permanently erase the deleted messages, using the menu Mailbox > Erase Deleted Items > In All Accounts... (or use the shortcut key shift+cmd+delete).
I think everything above is accurate, and I hope I've used enough key words and phrases that someone with the same problem might find this, and save themselves the 2 hours it took me to figure it out!
----------
Here's another tip for using Gmail via IMAP in Apple Mail:
Turn off the visibility of the Gmail All Mail folder in Apple Mail.
Go to Gmail via the browser, and enter Mail Settings > Labels, then UNCHECK "Show in IMAP".
Not only will this remove the superfluous folder from your Mail app, it will also keep Mail from downloading every single message twice (and those duplicates showing up in Spotlight searches).
I've done the same with the Spam folder, too.
----------
The same ability to delete (not archive) email is also possible using iOS 5+ on iPhone/iPod/iPad:
After setting up your gmail account on your iPhone, go back into Settings -> Mail, Contacts, Calendars -> (youraccount@gmail.com) and change the Archive Messages setting to OFF.
Now when you delete gmail messages on your iOS device they will be permanently deleted and not archived.