You are right that gases should solidify at low temperature, but the laser-cooled gases are so dilute compared to ordinary matter that they have metastability in their gaseous state. Three-body recombination, in which three atoms collide and two atoms form a molecule while the third atom takes the necessary momentum and energy to satisfy conservation of momentum and energy, limits the lifetime of the gases, if we ignore background collision. The only gas that would absolutely stay in the gaseous state at zero temperature is spin-polarized hydrogen (see the first paragraph in this paper on achievement of hydrogen BEC).
As for achieving nanokelvin temperature, actually it is hard to do this by laser cooling alone, unless the density is low enough. At high density, effects like photon re-absorption and light-assisted collision limits the size and the temperature of the laser-cooled cloud. Special techniques like velocity selective coherent population trapping (VSCPT) allowed cooling metastable helium gases to ~200 nanokelvin (see this paper by Cohen-Tannoudji) but the density was not high enough to see interesting effects like Bose-Einstein condensation. Usually you use laser cooling to reach many 10's of microkelvin temperature and then use evaporative cooling to get colder and denser.