Well, you can either go to your local BLM office and purchase a township and range map OR:
Go here:
http://www.esg.montana.edu/gl/trs-data.htmlUse the drop down menu to select NM; place the coordinates from the patent in the appropriate boxes and submit. BUT, sometimes this gives you a broad range of where the land is, and sometimes a more specific location--worth a shot.