"Are there other geographic divisions among the fae besides those that live underwater and those who live on land? Are there duchies/counties/etc. where one must be able to fly, or ones situated underground, or places of great heat or cold?"
Oh, are there ever.
The simplest way to divide Faerie is by element. You have land fae, water fae, sky fae, and "we live in a volcano, no, you can't come over for dinner, WE LIVE IN A FUCKING VOLCANO" fae (er, fire fae). Most of the Toby books deal with land fae, since Toby herself can't fly, live in lava, or breathe underwater. (Since this is a magical universe, she can do any of those things with help. She doesn't always have help. Or want help. Or hold still long enough to be helped, since "let me throw you in this volcano" is not her idea of assistance.)
That's the simple form.
The land kingdoms are divided into temperate areas (IE, anyplace where humans can live without major protective gear), along with frozen kingdoms, high desert kingdoms, and deep forest kingdoms. The elevation divisions—high mountain and underground—are technically considered "land," but are also considered "border zones" (more on this later).
Most of the land kingdoms are inhabitable by most of the fae races, with some exceptions. Land-bound water fae (undine, who are always fresh water, rusalki, who are water fae, but don't do oceans) can't survive in the desert; neither can the true cold fae, like the snow fairies, some of whom would actually melt. True desert fae, like the peri, don't like cold climates, although not all of them would die if subjected to cold. And naturally, most fae who live in a human range, like the Daoine Sidhe, will die of frostbite or dehydration if forced to go out without the proper gear.
The water kingdoms are divided primarily into fresh and salt; the Undersea doesn't include the freshwater fae, most of whom are treated as land denizens, due to lack of a coherent governing body in every single pond. The saltwater kingdoms are divided into the shallows, the middle-sea, and the deeps. Merrow can handle shallows or the middle-sea, but not the very bottom of the deeps. Cephali can handle the middle-sea and the deeps, but become very uncomfortable in the shallows. There are stories about some of the things that live in the deeps. Bad stories. For the most part, no one goes down there, because for the most part, people aren't idiots.
The sky kingdoms are the least divided, because, thus far, no fae have been confirmed capable of breathing in a vacuum. So they live in the clouds and pray no one flies a plane through their living room. Storm fae help with this. Good luck finding the capital city. It drifts.
The fire kingdoms are all very isolated, and very little is known about them, on account of the part where they're ON FIRE ALL THE TIME. They are the only kingdom which does not yet have reliable wireless.
Every kingdom borders on every other. Land/sea border = shoreline. Land/sky border = mountains. Land/fire border = deep caverns. Sea/sky border = more nebulous; usually weather patterns. Sea/fire border = deep rifts. And yes, there are fae basically everywhere. The land fae are the most accustomed, and adapted, to living with humans, and even they don't tend to like us very much.
Biology: Faerie does it weird.