I've noticed that some cave icons on my map have checkmarks next to them while others don't. What does the checkmark symbol mean?
In a similar vein as the treasure chest icon on shrines, a checkmark will appear on the cave if you've found the cave's Bubbulfrog and recovered its Bubbul Gem:
Once you’ve entered a cave and collected the Bubbul Gem, that cave will get a Check Mark on your map, so you know you don’t have to revisit it.
Like in the case of shrine chests, this implies that every cave will contain a Bubbulfrog. Keep an eye on the ceilings until you find it!