The diatomic oxygen molecule (O2) is paramagnetic because it contains unpaired electron spins. (If you don't know what this means try this brief introduction to magnetism.) Oxygen is paramagnetic whether it is gaseous, liquid, or solid, but the effect is much stronger when oxygen is cooled to the liquid or solid state primarily because of the increase in molecular density, i.e., more paramagnetic molecules per unit volume.
An additional effect is that all paramagnetic materials become more strongly magnetic with decreasing temperature. At elevated temperatures, the tendency of paramagnetic molecules to align with an applied magnetic field is opposed by thermal fluctuations that tend to randomize their orientation. These randomizing thermal fluctuations of course decrease with decreasing temperature.