So, I've been running this campaign for a group. Generally throwing fights at them that have been pretty close to the limit of what they can handle, they've had a lot of close scrapes, fought through it. But recently I accidentally threw one at them that definitely could have been a TPK if I hadn't had the enemies run off when half of them were defeated.

I'm not too happy about "saving" the PCs like that. Feels like I should let the story and dice fall where they will. On the other hand, it's not like the players did much wrong - I misjudged the power of some environmental hazards I put in, the players followed the obvious quest hooks and were reasonably cautious, over the course of the fight I didn't think they did anything particularly foolhardy. And it's not like there was any indication that this was an especially deadly encounter, it wasn't even a boss fight - in hindsight, the quest hook used for this level 10 party could have been equally used for a level 1 party, just with the party encountering different-level things to fight in the cave they ended up in! So it didn't feel good to just let it play out and be like well, the characters you've been playing for a year all just died in this random entrance for no real reason.

So I was thinking about how I could approach making a campaign differently to avoid this. I want do a hexcrawl-type game - give players a map, mark various points of interest on the map, have them pick which places they want to go. But the main thing I want is an in-game way of signalling the "difficulty" of a particular location or quest, so that then they can choose on their own - I can fill out the xp budget appropriately, and then let them deal with the natural variations of that difficulty.

I mean, I could always just mark things by CR or XP budget, but that seems immersion-breaking. Anyone have suggestions of how to, in-game or in-character, tell the players what the "difficulty level" of a particular area is? Or what information I could give them so that they could reasonably make decisions about where to go, where to fight, and when to run?

It's perfectly reasonable for an established threat to have lore associated with it that gives a decent idea of what kind of threat it is.

I've found that it's easiest to have an NPC talk about a difficult area. Just saying "That cave has taken the lives of many adventurers" might not do the trick. It's more of a temptation to players than a warning. But if you phrase it differently, you can give them a better idea. For example: say your group is all level 4, and has of a fighter and a wizard. Have your NPC expand on the earlier statement to include "The last group that came through was led by a Knight named Edward. He was a great fighter, his sword could cut twice when most could only cut once. He was joined by Daphne, a powerful wizard. She could cast great balls of fire out of thin air. They were joined by 3 others, just a capable. Even they fell to the horrors of the cave." 

Through that NPC encounter, you've given the "meta" information that a 5 person party, all at least 5th level, had a TPK in that cave. If your group is 4 level 4 PCs, they should be able to figure out they'll be a TPK also. You can tailor it based on your group's classes, levels, and size. Even though they have the map already, you can make it so that each location is just a general location, and have a town nearby so that there are NPCs to talk to, or maybe a library to research in, etc.

I won't tell them what "level" I think they should be to tackle something. But if they try to bite off more than they can chew I would probably say something like, "Are you sure you want to do that," or even, "You're welcome to do that but I just want to warn you that this might be a bit out of your league." 

So far they haven't tried to do that though... so I'm not sure how I will handle it if they do.

I mean they could have, right from the off. The backstory to our Roman Empire campaign is that one of the towns up north (and it is not far... maybe 100 miles from the starting town) was flattened by an unknown force, and that was 5 years ago. Rome has never been able to retake it, despite sending several legions up to get it back, and has at this point just withdrawn and given up. They could have said, at level 1, "let's go see what's up there." I would have reminded them that entire legions went and did not come back. But they seem to have realized this is not something to do at level 1.

At some point they will be able to go up there and if they don't take it into their heads to do so, I may give them a push (local magistrate asking them to go up for pay, etc.) which will hopefully signal to them, OK, you're strong enough to go up there.

But if they had insisted on going up there at level 1, well.. I guess there would have been a TPK...

There's nothing wrong with straight up telling them what they're getting into. "Hey guys, just letting you know that I as a DM like to run a more challenging, tactical game with harder combats. Is that good? Ok, you'll want to play accordingly. Let's do this."

For a hexcrawl-type game, I'd use something like Fallout 4's map, where encounters get progressively harder the further the players get from the starting town, and warn the players ahead of time. The freedom of choosing your own level of risk (and reward) is part of the fun of that style of gaming.

Study tactical games. It is all about information. Make sure that all information is available to the PC's in the world they inhabit. Lore books, songs children sing about the horror in the woods, corpses laying about... there are plenty of ingame ways to give information. Then it is up to them to use their resources to gain that information. If they happen to run into a situation unprepared and TPK...it is on them. Be very liberal with the information you give. Don't be stingy. This game is about decisions...so let them decide and prepare how they wish.