your wallet only needs to store your "keys" and nothing else. everything else is being stored publicly on the blockchain that is shared between peers on the bitcoin P2P network. in other words when someone sends you bitcoins, they aren't really sending "you" bitcoins. they are submitting the transaction to the public blockchain. and your "coins" (which are transaction outputs) are stored on that blockchain.
to spend those coins you have to provide a digital signature with your keys locally and then publish that signature so that you can move those "coins" and update the public ledger aka blockchain.
It's amazing that so many people still think of currency as a physical item, and can't quite grasp the notion that it's merely a digital representation of wealth. This isn't limited to cryptocurrency. Even USD is mostly digital these days. Conservative estimates suggest that physical dollars are used for about 26% of all USD transactions. Other estimates suggest that only 8% of the worlds wealth exists as actual physical notes and coins. The rest exists only in digital form.
@OP, think of it this way; your bitcoin isn't actually in your wallet. Regardless of what wallet software you use, the bitcoin is "stored" in the public blockchain. Your wallet contains private keys which act as "passwords" that allow you to move the bitcoin from one address to another. Once a transaction has been signed by a private key, the rest is handled by nodes and miners, and the public blockchain is modified to reflect the transaction.