Let's consider few realistic examples :
In our reality, France had to plant huge forests (Colbert) of certain trees in order to build a decent number of ships. It required special efforts, and you had to plan a long time in advance if you wished to have enough wood.
At this time, France was able to fight almost evenly the Royal navy.
Moreover a poor land, did not mean they can't grow trees.
England (Westeros is based upon it), is not really a fertile land since the middle age.
But nonetheless they got a really great navy for centuries.
Another example of small country with a huge fleet was the Netherlands. England had to wage three wars in order to reduce their naval power. They had a decent warfleet and a huge commercial fleet.
So considering the size of the Grey Joy navy. It is already surprising than they are able to man a fleet of one thousand ships. So it is rather unlikely that there is much wilderness or forest on the iron island. And anyway, it doesn't seem realistic to expect such small territory to grow enough wood for such a war fleet.
However the iron islands have direct access to some of the greatest forests of Westeros. They are close of the Twins. There is a huge forest between the Twins and Moat Caitlin. There is not many cities on the coastal lines but they may provide some of the wood.
Moreover the Greyjoys are know to been frequently seen next to the Bear Island, which is close to The Wall.
There is also a huge forest next to Winterfell and the West Coast.
So we don't definitely know how they got it. But they can easily buy it, chop it themselves (but I think it is unlikely), maybe stole it. But there is only small cities so if you kill the lumber guys, it is your loss.
If we think about the Free cities, they do not seem to have huge inland territories.
So naval powers like Braavos that are known for their trade, also more than likely buy woods from the North in Westeros.
Update : There seem to be a canon answer :
Archmaester Haereg suggests that need for wood was what first drove the ironborn to raid the mainland.
I got it from here