Go into Settings -> Mail and check the settings for each mailbox you have set up. There may be a setting to keep copy on the mail server. I personally use Exchange settings, so they differ to those you may be using, which may be either IMAP or POP3/SMTP. Each of the above mentioned accounts have their own quirks, so checking the settings is the the place to start.