I would like to offer a frame challenge. Given that you've supplied us with four possible ecosystems where fairies might live, each with different resources, I don't think you're actually asking about materials. I think you're asking about overall survival - how do fairies, despite being small and weak, survive in hostile environments? What would a fairy community need to look like in order to guarantee that survival? To give an idea of what I think fairy communities would look like, I want to talk about Beaver Dams.

Beavers create dams that disrupt the flow of a stream or river, creating an artificial island where they can build their lodge. Land predators can't easily get past the moat they've built for themselves, birds can't get in through the top, and as a special bonus, they've changed the playbook for most things that threaten them - by turning the river into a pond, more animals will come here to drink, creating an environment where stealth predators have a harder job because of how busy the area is likely to be.
Communities of fairies will only survive by working together, and the shelters they construct will probably have more in common with the beaver than with anything human. Rather than individual houses, they will build large, communal structures that can be subdivided on the inside, but which, like the beaver lodge, create artificial barriers for any and all potential predators, while also, by nature of their size and complexity, offer some change to the environment.
The forest fairies will likely make structures very similar to beaver dams, using any and all materials on hand. Given that there is a strain of fairy that lives underwater, I'm assuming all fairies can survive in water, meaning that the beaver lodge strategy where the only entrances are for swimming animals would still work. However, i think the fairies would also create an emergency exit near the top, a somewhat loose area in the construction that could be broken from within so that if the river flooded, the lodge could be abandoned and all the fairies could fly out in a swarm.
Obviously, the Desert fairies won't have rivers to dam. They can't copy paste this approach. What they can do, however, is move dirt and farm cacti. What I'm imagining is something like a termite mound, but surrounded by a grove of cacti.


Fairies would make natural pollinators, and being intelligent and social, it would be easy for them to use this to control the plant life of their surroundings. In other ecosystems, this wouldn't add much to their natural defenses, but in the desert, where plants come with defenses of their own, it would be very advantageous. (Now that I think of it, Forest fairies may actually do the same thing, seeding blackberry and other thorn bushes around their construction if they can't easily redirect a river)
From here, the other two strains of fairy are just extensions of these approaches. Underground fairies build the mounds, but in places where cacti don't grow, so they make the mound less conspicuous, pushing further down into the earth and creating more intricate, hidden colonies wither entrances and exits all across a large swath of land, maybe even taking advantage of existing cavern systems to do so. Underwater fairies make lodges, but instead of artificial lakes off of a river, they are making artificial tidal pools off of a coastline, using clam shells and seaweed as much as driftwood to make more watertight constructions.
These constructions would collectively be called Fairy Castles. I imagine fairies living in groups of 50 to 100, building these castles together, and then digging into the ground or into the walls they've built to create family enclosures inside the castle. Depending on where the fairies live they build their castles out of what's available, and keep them intact and and in good repair for however long they need it for. Some fairies may build seasonal castles, some may build ones that last for a few years (long enough for children to grow to adulthood, for example), some may build ones that are effectively permanent. The fairy groups may or may not have heirarchy, may or may not cast out individuals who don't cooperate with the group, but the central idea is, living together as a big collective allows them to make complex structures like this, and increases overall survival rate.