For New Mexico convictions, only juveniles who were under 18 years of age have their children's court records sealed. Expungement of adult felony records is not possible.
Most states have a process to seal/expunge old criminal records if certain conditions relating to time elapsed and the nature of the original conviction are satisfied. You will need to consult with a local attorney to determine for sure if you can satisfy those conditions. If so, it is usually a simple matter of filing some papers and paying some court fees (and attorney fees if a lawyer does it). Note that often you will need to have separate processes to address the court files as distinct from the arrest/police records because they are entirely different systems.