How e-mail is stored is not all that complicated, at least for POP3 and IMAP, which are the two most commonly used protocols.
Simplified (because there can be some tweaking, but the concepts still apply:
POP3: e-mail messages are stored on the e-mail server only until they are accessed by the e-mail client, at which time they are downloaded to the device that is accessing them via POP and they are removed from the server. If you have multiple devices accessing the same account, all using POP3, they are destined to get out of sync because "whoever got the message first" is the only place where the message will be present and stored. For all other devices it doesn't exist when they go to query the server after the first device has snagged them.
IMAP: e-mail messages are *all* stored on the e-mail server permanently until the user deletes them. And all folders that one creates on the e-mail client for sorting purposes are, in actuality, created on the server. When e-mail is accessed via a client what generally happens is that all new e-mail message headers are downloaded (think of the subject, from, date) and the message body is only retrieved when you actually open a message to read it. Because it is entirely possible that one might be offline when you want to read recent messages, most e-mail clients also download the message bodies for some set timeframe, say two weeks. When a message ages past two weeks the message body is deleted, because it can be retrieved again from the server if it's needed later.
POP3 is what is called a client-side protocol The server is pretty much nothing but a pipeline that transports the messages to your computer for permanent storage.
IMAP is what is called a server-side protocol. The server is the "master coordinator" and all clients that access the server are essentially letting you see what's on the server, and downloading only what's necessary for you to read messages if/when you want to read them. This allows all clients to appear as though they are in sync with each other when, in reality, they're all in sync with the server.