N.M. Stat. § 70-4-1
Every person who shall, by contract, express or implied, or partly expressed or implied, with the owner of any land, oil and gas permit, leasehold, lease for oil and gas purposes, or with the owner of any gas, oil, or gasoline pipeline, or with a purchaser under executory contract, or with the trustee or agent of the owner, or with one whom the owner has authorized or knowingly permitted to contract, or with a receiver appointed for any of the property of the owner, perform labor or furnish or haul material, equipment, tools, machinery or oil well or gas well supplies, used or employed, or to be used, or to be employed in the digging, drilling, torpedoing, completing, maintaining, equipping, operating or repairing any oil or gas well, or in the construction, operation, maintenance or repairing any gas, oil, or gasoline pipeline, or who shall furnish or haul any oil or gas well supplies, or perform any labor in constructing or putting together any of the equipment or machinery used or employed, or to be used or to be employed, in drilling, torpedoing, completing, maintaining, equipping, operating, or repairing any oil or gas well, shall have a lien upon the whole of that land, oil and gas permit, leasehold, lease for oil and gas purposes, oil pipeline, gas pipeline, or gasoline pipeline, and right-of-way therefor, the buildings and equipment thereon, and the appurtenances thereto, the proceeds from the sale of oil and gas produced therefrom inuring to the working interest, and upon the materials, tools, machinery, equipment and supplies so furnished or hauled, and upon the oil and gas well for which they were furnished or hauled, and upon all the other oil and gas wells, fixtures, machinery, tools, equipment and appliances, used or employed in operating or developing, for oil and gas purposes, upon the land, oil and gas permit, leasehold, or lease for oil and gas purposes, for which the material, tools, machinery, equipment or supplies were furnished or hauled, or labor performed, for the amount due to him for the materials, tools, machinery, equipment, oil and gas well supplies, hauling, or labor, and interest from the date the amount is due; provided, however, the lien herein created shall not extend to the underlying fee or royalty interest unless expressly provided by contract, nor shall it extend to the property, leasehold, or working interest of any owner who does not have a working interest in the well upon which the labor was performed or for which the materials were furnished or hauled.
The lien shall be preferred to all other liens or incumbrances which may attach to or upon the land, oil and gas permit, leasehold, lease for oil and gas purposes, and the buildings, machinery, equipment and appurtenances, or upon any oil pipeline, gas pipeline, or gasoline pipeline, and the right-of-way therefor, or such oil or gas wells, the proceeds from the sale of oil and gas produced therefrom inuring to the working interest, and the material, tools, machinery, equipment and supplies so furnished or hauled and the fixtures and appliances thereon, subsequent to the commencement of the labor performed, or the furnishing, or hauling, or putting up of the material, tools, machinery, equipment or supplies; and the lien shall follow the property and each part thereof, and be enforceable against the property wherever it may be found. The taking of any note or additional security by the contractor or subcontractor, or the person having the lien shall not effect, or be a waiver of, any lien he may have by virtue of the Oil and Gas Lien Act, unless made a waiver by express agreement in writing of the parties; and the lien hereby given shall attach as of the date on which the first of the material, tools, machinery, equipment or supplies is furnished or hauled, or the first of the labor is performed. Any purchaser of oil or gas in the ordinary course of business without actual knowledge of the filing of a lien covering the proceeds from the sale of oil or gas shall take the oil or gas free of the lien.
NMS § 70-4-1