Censusreporter.org 
Table B25040

Perhaps median gross rent minus median contract rent?  Shaky to perhaps worthless results but a starter type result?  

Hi Gwendolyn - 

You might look into Regional Price Parities (RPPs) from the Bureau of Economic Analysis (BEA).
Regional Price Parities, Real Personal Consumption Expenditures, and Real Personal Income | U.S. Bureau of Economic Analysis (BEA) 

They have utility expenses by state and by MSA:

Thanks so much, Tim. But, these aren't cost estimates, right?

Try your state's public utilities commission?

Would the American Housing Survey provide any useful data?

I thought so, too, but the housing survey seems to have limited coverage.

Thanks, Cliff. It doesn't look like New Mexico is one of the sampled states. ???

If you can use PUMS data, they have cost of utilities.

Thank you, Dave! Please, could you walk me through how you got to this "Regional Data GDP and Personal Income" screen?

Yes, that is a bit tricky.  You can find the data in the BEA's interactive data tool:
Interactive Data Application | U.S. Bureau of Economic Analysis (BEA)

I used the following steps:

• Under Regional Data on the left, click on Gross Domestic Product and Personal Income
• Click on Interactive Data Tables
• Near the bottom of the list of tables, click on REAL PERSONAL INCOME (RPI), REAL PERSONAL CONSUMPTION EXPENDITURES (RPCE), REGIONAL PRICE PARITIES (RPPS), then click on Regional price parities (RPPs)
• Select SARPP (by state) or MARPP (by MSA)

The values are relative costs - a value above 100 is more than the average, etc.  I'm not sure if there is a way to tie these values to actual dollar expenses.  

Oh sorry I sent you a table without costs. Here's one with costs -- they do collect it for ACS so keep looking! We used to do annual looks at property taxes, another component of owner costs, so I know with a little patience you can unearth this 

data.census.gov/table

Thank you, Douglas. I was able to download some PUMS data tables. Now if I could simply figure out how to decipher them. I really only want to know if the cost of utilities has increased in New Mexico over the past several years.

So, the "SARPP Regional price parities by state" is the average cost of utilities???

Gwendolyn - 

The BEA RPPs are relative costs - how much more or less this state pays than other states.  For actual dollar costs, the BEA Personal Consumption Expenditures (PCEs) are probably more appropriate. There is a table: SAPCE3 Personal consumption expenditures (PCE) by state by type of product.

This table gives total costs across the area for different expenditures. Here is a link that should take you to a table of costs for New Mexico for the last 5 years for household utility expenses:
BEA Interactive Data Application

For a per person or per household value, you would need to divide by the appropriate denominator.  

BTW, the BEA data are derived from ACS PUMS data.