Also, I suspect that early settlers in the US couldn't find the clay they needed to make brick

You've obviously never been to North Carolina. (The Roanoke (Lost) colony was either in southern Virginia or northern North Carolina.) There is nothing but nasty red clay as far as the eye can see. Right on the surface. At the same time, trees were probably more readily available and needed to be cleared an order to build a structure anyway.