I know that sound travels faster in water compared to air and say, faster in steel than in water so, What would the density have to be to cause sound to approach the speed of light?
Have a look at http://en.wikipedia.org/wiki/Speed_of_sound#Basic_formula for info on how the speed of sound depends on the medium it's passing through.
Generally the important factors are the stiffness of the medium and it's density. To get sound to travel faster you need a stiffer lighter medium. For ordinary matter you'll never get speeds at anything like the speed of light because the electromagnetic forces that hold matter together are far too weak to permit this. However in neutron stars the stiffness of the degenerate matter they're made from is determined by nuclear forces and the speed of sound can approach the speed of light.