The Bureau of Labor Statistics spends a few billion each year on a "secret shopper" program; every few weeks, one of their people walks into a store with a shopping list, more or less, and writes down the prices of this "basket" of goods at the store. Other agents do the same thing at other stores on other days, and the results are input into a huge data farm that spits out various statistical breakdowns, including the overall number, the Consumer Price Index. This data is available for specific regions, including major metro areas, and can be easily viewed here.
This data is pretty much the best we have available to use to determine the relative "cost of living" in various parts of the U.S.. If your current and probable destinations are listed by name (or close enough), you can look at the various categories and compare relative costs to compute a percentage difference.
Most "cost-of-living" calculators do this very generally, based on relative average CPI numbers between the two metro areas. If the overall percentage difference in CPI between Dallas and Denver is 3%, they'll say it's 3% more or less expensive. You can do better, by going down the list of your own monthly expenses and looking up the numbers in the two metro areas for each of them and computing the real price difference, then weighting those differences by the portion of your budget you'd typically spend on them. For instance, there's an entire section on tobacco that figures into the overall average; if you don't smoke, it doesn't apply to you, but a pack-a-day smoker would be very interested to see the difference between, say, Atlanta (virtually no state excise taxes) and NYNY ($4/pack in state taxes).
One major thing you may want to consider separately from any government number is home prices. The CPI simply cannot be calculated at a granular enough level to really take variations between neighborhoods of a metro area into account. For that, I'd be looking at numbers on real estate sites, trying to find "comparables"; homes with similar construction, age, sqft, beds/baths, amenities, etc in neighborhoods of similar demographic makeup. These can vary widely; in DFW, I bought a 1675 sqft 1.5 story for about $140k. My brother in Pittsburgh is looking for a similar home and finding prices at about the quarter-million mark (the big difference being that the plots on which homes are built in Appalachia are bigger, because the average grade of that plot, and thus the amount of land rendered unusable by landscaping for foundation grade or natural terrain features, is bigger as well).
And don't forget taxes; states all make their cut in different ways, and those taxes don't always show up in CPI numbers (excise taxes usually do because they are included in the sticker price of specific goods like gas, tobacco or trans fats, but sales/use taxes are usually not counted because they are applied very generally to the subtotal of your shopping list). The three main taxes will be income, property and sales/use; most jurisdictions will use two out of three, and these will compound between state and local (so you may have to figure all three, if the state uses an income tax but the city has property and sales taxes). They usually don't differ inside metropolitan areas, but they can, and they can vary widely between regions of the same state and between towns on opposite sides of a state line that are geographically close (for instance, the St Louis metro includes the city of East St. Louis, which is in Illinois).