There is no restriction other than $c_s<c$. Relativistic plasmas and fluids explore this regime. A weakly coupled quark gluon plasma has $c_s=c/\sqrt{3}$. Even higher speeds are reached in neutron stars, see http://physics.stackexchange.com/questions/54684/is-the-speed-of-sound-almost-as-high-as-the-speed-of-light-in-neutron-stars .

The speed of sound is related to the adiabatic compressibility
$$
c_s^2 = \left(\frac{\partial P}{\partial \rho}\right)_s \, . 
$$
This quantity also enters the neutron structure via the TOV equation. It constrains, in particular, the maximum mass and the mass-radius relation. The recent observation of a 2-solar mass neutron star implies that $c_s$ becomes quite large, certainly bigger than $0.5c$.

Adendum: See [here][1] for a more quantitative analysis based on the existence of a 2 M(solar) neutron star, and equ.(10) of this [paper][2] for a theoretical limit in which we can shows that $c_s\to c$. 


  [1]: https://arxiv.org/abs/1408.5116
  [2]: https://arxiv.org/abs/0905.0903