Mexican civil registration began in 1859, after the war with the United States, but wasn’t widespread until 1867. The FHL has microfilmed civil registrations from thousands of local offices (municipios) across Mexico, each of which could encompass several towns. Some of these are also online at FamilySearch.org.
State archives in the US Southwest often include records dating to the Mexican era. New Mexico, for example, has early censuses, land records and Catholic church records from the Archdiocese of Santa Fe (also on FHL microfilm). The New Mexico Genealogical Society has been extracting and publishing these early church records. The Mexican Archives of New Mexico are in Albuquerque’s Special Collections Library.
Several published indexes cover Mexican censuses for what’s now Arizona: 1801 for Pimeria Alta; 1831 to 32 for Tucson, Tubac and Santa Cruz; and 1852 for Pimeria Alta. You can find early documents, such as the 1831-32 census of Santa Cruz County, at the state archives and the Arizona Historical Society.