Help with Mail - where is it stored

Hi, I'm hoping someone can help me. I received an email warning from my provider (road runner) that my mailbox is 70% full and I may not get all my mail. I then learned that I am indeed not getting some friends' mail.

Can someone tell me where mail is stored in Mail? If I empty mail in the ON MY MAC section, will it make room on the server or is the mail actually all stored somewhere on my mac and I should look elsewhere to make room on the server?

I have gotten rid of all sent mail from 2008 and earlier and all trash and junk are empty.

Mahalo for your help~
Denise