They're hardcoded to only spawn in meadows and another biome, I think. Maybe plains.
Once you get to those biomes, however, prepare to see redwood trees everywhere.
They seem to gen a bit randomly in the sky above the normal cloud layer, nice and fluffy fall savers. Nether clouds gen in the higher areas where there is open space, they come in sulfur and ash flavors.