What type of mail service do you have? Gmail? Yahoo? Through your ISP? Mail doesn't have any 'quota' limits - that's usually handled on your mail provider side. And, AFAIK, and depending on what type of account you have, you just delete mail by selecting a message and hitting the delete key - when you quit Mail those messages will (again, depending on what sort of account you have) be purged from the mail server.
I use Gmail, as well. But I don't use Mail, I use Microsoft Outlook - however, both should operate the same.
Is your account set up as an IMAP account? That's what I use - constant connection and when I quit Outlook (as should happen when you quit Mail) the mail files on the Gmail server are purged. It's odd that you're exceeding some sort of Gmail quota, though. I get about 300 messages a day - some with attachments - and send out about 50 messages a day (some with large attachments) and I've never hit a quota limit (take a look here - http://support.google.com/mail/bin/answer.py?hl=en&answer=6558).
It seems as if your mail isn't being purged... is your account set up as IMAP or POP (I recommend IMAP)?