How do we get supersonic bullets?

The speed of sound increases with increasing pressure. Assuming ideal behaviour the relationship is:

$$ v = \sqrt{\gamma\frac{P}{\rho}} $$

or equivalently:

$$ v = \sqrt{\frac{\gamma RT}{M}} $$

where $M$ is the molar mass.

In a gun barrel just after the charge has gone off the gas is under very high pressure and very hot, so the speed of sound is much higher than under ambient conditions.

Deflagration means that the combustion moves through the fuel slower than the speed of sound in the fuel. It doesn't say anything about the speed of the resulting gas, or how it compares to the speed of sound in that gas (and the speed of sound in solids is generally higher than that of gasses). The gas that is released from the combustion isn't at equilibrium, so properties such as "pressure", "temperature", and thus "speed of sound" aren't fully defined for it.