I fly a lot in Utah, Arizona, New Mexico, so I keep abreast of the rules.
On BLM and US Forest Service land, you can fly anywhere within FFA guidelines and rules, unless it is posted otherwise, which is rare. In addition, you can fly on National Monuments and National Recreation Areas that are administered by the BLM, which is usually the smaller and more obscure ones. Check in advance to see which agency is running the place.
National Monuments and National Recreation Areas run by the National Park Service are totally off limits to drones, as are National Parks. So, drone rules in federal parks vary with the managing agency, not the title of the park.
State parks in Utah each have their own drone rules, so you have to check with each park office separately. For example, Dead Horse Point State Park allows drones during winter months with a $25 fee, but they're prohibited in other seasons. Goosenecks of the San Juan State Park is so small and lightly visited that it is hard to find the right person to talk to, so I fly first and ask forgivness later. Etc.
I don't know policies for state parks in Arizona and New Mexico.
Native American lands seem to work this way: If a visit permit is required, for example Monument Valley, drones are prohibited. If a permit is not required, check with the local town, chapter house, or village. In really remote areas, nobody seems to care.
But in all areas, including private lands, FAA authority applies.
