Density is only an issue as it pertains to what the medium is. The speed of sound is faster with hydrogen than air, for example, due to hydrogen being less dense. It is important to notice that the speed of sound INCREASES with DECREASING density, while it also INCREASES with INCREASING temperature. This is all in a gas, incidentally. The speed of sound in a solid object is not particularly affected by the temperature as the elasticity is due to atomic properties and not molecular motion.
This elasticity can be thought of as a "restoring" force, bringing the object or fluid/gas back to its original state. The faster this happens the faster sound will travel. The stiffer the substance is the faster it restores so the faster sound travels. Stiffness refers to the change in pressure due to a change in volume.
Elasticity, therefore, is related to temperature for a particular gas or the inter-atomic forces in a solid object.
Sound is directly proportional to the stiffness and inversely proportional to the density. The only way to change the density in this sense is to change the gas itself. If you decrease the density, all else equal, the sound will move faster. This is why people sound funny when they've inhaled helium.