I hope this clears things up: http://www.sciencenet.org.uk/database/Physics/Rockets/p00845c.html
I’ve tried to find out what the nature of the “oxidizer” is, but I as of yet I haven’t succeeded. Clearly, solid oxidizers (saltpeter is one, as has been mentioned) are not a recent invention; modern gunpowders can work in vaccuum since they contain solid oxygen-containing compounds as well. I don’t know what they are though; I seem to remember the firearm propellants being based on nitro-cellulose but I don’t know if that’s the state of the art.
There are some exceptions to the solid-fueled rule for military rockets. The Titan is (or was) a liquid-fueled rocket, used both for large nuclear warheads and putting spacecraft into orbit (Gemini, if I remember correctly).