The neutron star crust is separated into outer and inner regions. The outer is a crust of neutron-rich nuclei surrounded by degenerate electrons. The inner is similar, but the nuclei are even more neutron-rich and there are degenerate neutrons too.
The (qualitative) answer to your question looks at the ratio of electrostatic (Coulomb) energy to the thermal energy of the ions in the crust.
$$\frac{E_c}{E_{th}} \simeq \frac{Z^2 e^2}{4\pi \epsilon_0 r_0\ k_B T},$$
where $T$ is the temperature, $Z$ is the atomic number of the nuclei and $r_0$ is a characteristic separation between the nuclei.
This ratio increases with: decreasing temperature, with decreasing nuclei separation (ie increasing density) and increasing atomic number. When it reaches some critical value (roughly 150-200), the plasma "freezes" into a crust, with the ions locked into some solid lattice. The same phenomenon occurs in the cores of white dwarfs at similar temperatures and densities, and the process has been "observed" to occur via asteroseismology.
So what is going on here, is that although the crust is hot ($10^{7}$ K would not be unreasonable actually a little way below the surface), the densities ($10^{11}-10^{15}$ kg/m$^3$) are high enough to solidify the plasma.
This is of course not the whole story. At very high densities, when the neutrons drip out of the nuclei, one has to consider surface energy terms and ultimately the neutron fluid "dissolves" the crust at about $10^{16}$ kg/m$^3$, possibly via several bizarre "nuclear pasta" phases, eventually forming a fluid of neutrons, protons and electrons.
The crust material is comparatively compressible/soft compared with the neutron star interior, in that it has a lower adiabatic index. However, in absolute terms it would seem incredibly hard (by 20 orders of magnitude) compared to say something like diamond, because of the extreme pressures present ($10^{28}-10^{35}$ Pa), which are roughly equivalent to the bulk modulus.