Cryogenic treatment is an acceptable form of improving heat treated (quench and tempered) steel. This treatment has been studied and is accepted in the proferrional engineering community. Beyond that it become more like snake oil treatment.... hence it sometimes gets a bad name because some treaters expand this service beyond its accepted scope.
Let me see if I can keep this simple. What this treatment accomplishes is that it converts the soft retained austenite in hardened steel to hard martensite, gaining more available hardness and strength to a part, and rendering the part more stable by heading off any future retained austenite conversion that often happens during use. Depending on the alloy, process, and heat treatment, retained austenite levels can sometimes reach up to 50% in some parts.
Proper cryotreatment involves incorporating this step some time before tempering of a quenched part. You can't just willy-nilly take a heat-treated part in the finished condition and cryotreat it. The newly formed martensite will be brittle and provide crack initiation sites under load or Hertzian stresses.
Cryotreatment is best suited for small hardened steel parts that are expensive to manufacture such as machine cutting tools. It's been shown to improve tool life dramatically... 300% gain is not unusual. Large parts consume more liquid nitrogen and aren't as economically viable to cryotreat.
For non-heat-treated steel, cryotreatment may relieve some stresses - I'm not sure - but stress relief is better accomplished by heating a part - not chilling it.