If you look at this diagram:
The power supply cap is the 100uf in the upper left corner that connects on the pin 6 of the LM386. You could try putting a 1000uf and a 47uf in parallel here to help with the power supply. However, I highly suspect that you are maxing out the 1 watt power output fast and that's why the sound quality is dropping as you turn it up. This is not a powerful amp and the circuit is really meant for experimentation.
you'll probably have better success searching and posting in the diyaudio.com forums.