If you want more gain, you have three options.
The first is using a transistor with a higher gain as Zener suggested. h(FE) for the 3904 is probably about 100, whilst the 2839 looks to go up as high as 160+. That's certainly one way to take care of it.
The second is to use a
Darlington pair. It's basically using two transistors, where one just feeds into the base of the second one, so the second amplifies the output of the second. It's cheap (since you probably have a second 3904 lying around) and it's powerful: You can go from a gain of 100 to a gain of 10,000 (100 * 100 - yeah, that's the math.) That's it's problem, though: It's powerful, but perhaps too powerful. If you need a gain of, say, 250 instead of 10,000, then you're overshooting. By a lot. Using a darlington is a bit, ah... ham-handed.
The final option is to use an
op-amp. An op-amp will basically allow you to construct a circuit with any gain you see fit. For example using this circuit:

...will give you a gain of Rf/Rin. So just set Rf at 10K and Rin at 10 Ohms, and you've got your 1,000 to 1 gain. Or whatever you feel like setting the gain at. Or you could use a POT, putting the middle pin at the junction between Rin, Rf, and the "-" terminal and you've got an adjustable gain amplifier.
Seriously, op-amps are awesome, and if you want to do any real audio work you'll need to use them. However, there are drawbacks. First, you need to go out and buy it. They're not expensive, but you may need to wait a while. Hopefully your Radio Shack has one in that "cabinet-of-random-crap" that they keep in the back. Usually they do. Secondly, and more importantly, op-amps require two voltage supplies in addition to ground. V+ and V-. V- is the NEGATIVE power supply. So you need to be able to generate a negative voltage reference, equal in magnitude to your V+. Now, mostly people don't really generate negative voltage. Mostly they just cheat, by setting a virtual ground with a voltage divider or using the dropouts from diodes. I imagine Adafruit cheated in their wave shield, actually, because they use an op amp in that circuit and I can find no negative power rails. In fact, you can
see for yourself they just use the regular ground for the negative supply. (It's that pair of op-amps in the upper right of the image.)