A classical bit can store two states: 0 or 1. It is always one of them, it does not change "on its own" and you can measure it without changing it. For every additional bit you add, you double the amount of possible states. Thats an exponential growth in the number of states when linearly adding bits. Something like $s = 2^b$ with number of states s and number of bits b.
A qubit works different: First of all, it can be in a superposition as you stated. I like to think of this state (still incomplete) as some kind of float: A number between 0 and 1, expressing somehow the probability for the qubit to become either 0 or 1 when measured. You would get pretty much the same effect by calling e.g. 64 bits a qubit, so thats not yet it.
The next effect that hits is entanglement. Let's say you describe a qubit with a 64 bit float. If you add another 64 bit float, is that enough to describe a system with 2 qubits? 2 qubits might be in a state where you know they are always the same, so if you measure one to be 0, you know the other one is 0 as well, and if you measure 1 you know the other one is also 1. But both cases are equally likely. How would you describe this with just one float for each qubit? Is it (0.5,0.5)? But thats the same as "Both are totally random"? Do you take one float for the first qubit and the second for "equals to the first or different"? But then you can't describe "totally unrelated but each with different probabilities" anymore? You would actually need 3 floats to describe the entire system, one for |00>, one for |01>, one for |10>. Since the total probability needs to be 1, the last one can be calculated. To describe a system of n qubits like this, you would need $2^n - 1$ floats. Thats an exponential growth in bits needed to represent a linear growth in qubits, somewhat like $ b \approx 2^q $ with number of bits b and number of qubits q. 783
Remember the first paragraph? That means $s \approx 2^{2^q}$.
When looking even closer, qubits also have something called phase. Basically theres different "directions" a superposition between 0 and 1 can have. The Bloch sphere is a graphical representation of this for single qubits. So you not only need to describe one number between 0 and 1, but actually 3 of them. And this exponentially growing with the number of qubits...
All these information, all these different states, the different possible outcomes with their probabilities are "encoded" if you want in the actual qubits. If you measure them, they are gone and no more useful than the same number of classical bits. But if you don't measure them, they are there, they are real. You can invert possibilities. You can "mix" them. You can change a qubit dependent on the state of another qubit. Theres a lot of computations you can do without measuring, without forcing the qubits to either become 0 or 1. And if you then manage to reach a state at the end, where the measured outcome is not "random", but dependent on your calculation, you found a quantum algorithm. A bit like the classical check for even or odd integers, where you only need to check the last bit and this gives you an unambiguous answer.
Examples are the Deutsch-Jozsa algorithm as mentioned by <PERSON> or the famous <PERSON>'s algorithm. They are strange, you can't "debug" them in the middle and measure their state, but at the end they give a result.
TL;DR
Qubits are awesome. They carry a lot of information and if you don't measure them, you can do stuff. 783