Are my coins stored in the wallet, or where the heck are they? This is a very good question, because the answer defines what your wallet actually needs to protect.
Cryptocurrencies are called like that because they are secured by cryptography. For this purpose, you need a set of digital keys, for example your (very secret) private key. With this key you can encrypt and digitally sign things.
Now let’s take Bitcoin as an example (other cryptocurrencies work in a similar way). The whole Bitcoin network is kept in sync through a shared data structure, the blockchain. It contains records of all the transactions ever made and is publicly available online, so it can be read by anyone. If you receive some bitcoins, let’s say 0.1 BTC, you see them in your Bitcoin wallet, listed under a Bitcoin address.
Your bitcoins are not actually stored in the wallet, they’re just an entry in the public blockchain. What the wallet stores is your secret private key that belongs to that address. Because you control this private key, you can spend these bitcoins: this is how “Bitcoin ownership” is defined. Everybody can see these bitcoins, but only you can spend them, so they are yours. But this also means that everyone who has the right private key can spend these bitcoins. This is why it’s very important to keep this key a secret.