Some of these questions have been answered already, so you might find additional answers using the search.
Yes, in the classical case, if you have $n$ bits, you have $2^n$ different "messages" that you can encode and the state of each bit is all you need to describe the state of the systems.
In the quantum case, if you have $n$ qubits, that is $n$ 2-level quantum systems, you also have $2^n$ different "messages" you can encode (never more), for, as you say correctly, when you measure, you obtain an $n$-bit string. If you want to play encoding/decoding, however there is more you need than in the classical case: You need to know the basis in which to measure your state.
If you want to have a complete knowledge of the state, then, as you said, you need many more parameters - essentially the amplitude (which is a complex number) for every possible measurement outcome. That's $2^n$ complex numbers (normalization aside). So what's the number of states? That's not an interesting answer - it's infinite. However, you can't do anything with them. In order to use them, you'd ALWAYS need the knowledge of the $2^n$ amplitudes. Otherwise all you can retrieve is $n$ bits. Given $n$ qubits, you can always only store and faithfully retrieve or send and faithfully receive $n$ bits of information (without noise). This is called the "Holevo-bound".
Before you go on and get confused: There is something called "superdense coding", where they tell you that you only need one qbit to send two bits of information. That's somewhat true - but it's also "cheating". The reason is that in order to do this, you need to have a preshared pair of entangled qubits - so in a sense you have to send two qubits: one bit when sending a message and another, before you even know what you are going to send later on. If you don't consider preshared entanglement, the Holevo-bound is as good as it gets.
So where is the speedup? As I already said, the accessible information is not more than in classical information, however, the superposition does seem to become handy. For example, if we want to simulate a physical system with, say $n$ qubits, we'd have to keep track of all $2^n$ amplitudes in a classical computer. The real-world quantum system, however, of course only needs the $n$ qubits.
How about algorithms? I'm not really an expert on this, but there are not yet many truly different algorithms that actually offer a speedup compared to classical algorithms. Shor's algorithm of course is a candidate - but then, we don't know whether factoring is maybe not efficiently solvable on a classical computer after all. Grover's search is a real speedup. It's "just" a square-root improvement, but at least it's something (as far as I know) that a classical algorithm definitely can't do.
In short, we don't really know how much more powerful QC will be - except for simulating quantum mechanics. As I see it, there is also no simple reason as to why QC can be more powerful (such as: "It contains much more information" - no, it doesn't, "It can do all computations at once" - no, it can't, see Scott Aaronson's blog http://www.scottaaronson.com/blog/ for more on that). Mostly, the results are based on some structure that can be exploited differently given quantum mechanics.
