Were there trees in and around the Venetian lagoon? Yes and no. One of the things that many modern visitors to Venice, as well as casual readers of Venetian history, must really understand that in late antiquity, the Venetian islands did not look much like they did now. This is what many of the Venetian islands would have looked like for the first three or four hundred years of their existence, and what would be called the "Republic of Venice" was initially the government of a multitude of disjointed and relatively sparsely populated island communities, with more than enough lumber to meet their immediate needs. But the story of these brackish water island communities is a very long one. I will try to narrate the social, economic, and political factors that influenced the very colorful events that led to Venice's dominance over the Adriatic, and ability to project itself across the eastern Mediterranean, however each and every single event could open up all a manner of additional discussions, which I very much encourage!

Edit: At least one post has offered a TL;DR. I have not included one, in spite of the long, sometimes winding two-thousand+ word text mostly consisting of narrative history (with some analysis) I have posted below. There are two reasons for this, the first is that there is no single reason why Venice became a naval power between the 13th and 16th centuries, in addition to there being no single reason why it was able to survive and thrive as a polity for over one thousand years. The second is that before we can ask why Venice occupied the role it did in the Mediterranean, we have to examine the myriad ways how, which each how tied to its own why.

Coastal northeastern Italy was a Byzantine military outpost up until the Byzantine's center of command in Ravenna fell to the Lombards in the eight century. Now, Ravenna is conveniently located south of the mouth of the River Po in a sort of swampy marshland by the sea, and its sandy tidal basin had housed the Second Italian Fleet (the Classis Ravennatis) since the 1st century. Further, Ravenna was the starting point for a system of canals that connected it to all of the lagoons of the northern Adriatic coast all the way up to Aquileia. These strong ties to the sea meant that northeastern Italy could easily receive garrisons, material, and other resources from the Eastern Empire; further linking this part of Italy to seafaring, and establishing particularly strong connections to the east.

When Ravenna was under siege in 751, no Consul was appointed to govern the northeastern lagoons that year. The people resolved to elect their own Dux, or leader (a title which would quickly be corrupted in the local Vulgate to "Doge"). When Ravenna fell and what was left of the Byzantine army evacuated to Bari, this man (named Teodato Orseolo) found himself the ruler of an independent polity.

The early Venetians would understand very, very early on that the lagoons were not only a convenient place to moor ships or cast their fishing nets, but a vital natural barrier guaranteeing their independence and survival: the first of and arguably most important of many factors guaranteeing stability and prosperity. In fact, not long after the Lombard conquest of Ravenna, the Lombard Kingdom of Italy turned its attention to Rome. Pope Adrian consequentially called to the Franks for aid, and Charlemagne spared no time to descend onto Italy and make quick work of the Lombards, asserting himself in northern Italy and granting the Papacy a large temporal territory to govern. Pepin, Charlemagne's son who had been assigned the Kingdom of Italy, soon realized his father had overlooked the northeastern lagoons, and set out to secure their submission.

How effective the armed citizenry of the Lagoons could be against the landed-warrior-levy of the Franks is up for speculation: a decisive battle was never fought. Pulling up buys and markers so that only the most experienced navigators could sail in the shallow waters of the lagoon, the Venetians limited Pepin to the islands of Chioggia and Pellestrina in the southern lagoon and the communities of Grado, Jesolo and Eraclea to the north. Once the King arrived in the channel of Malamocco, he found sharp stakes driven into it, making easy crossing impossible. The Venetians pelted the Franks with arrows as they tried to wade the waters, and the Franks soon withdrew. They found they had to crowd onto the thin island of Pellestrina (which was obviously not nearly as built up as it is today) and stay out of sight of the shore: the Venetians in their narrow riverboats circled them like hungry sharks, their arrows picking them off one at a time (and when the Franks were looking particularly short on supplies, the Venetians even threw bread at them). Eventually, Pepin negotiated to have a large tribute paid to him and left.

So clearly, in the tumultuous post-Carolingian pseudo-crisis, it certainly helped that the communities of Malamocco, Eraclea and Grado were each separated by the mainland by lagoons up to 500km^2 of brackish water. Sure, the lagoons are only waist-deep in most places, but approaching an enemy over nearly two hundred square miles of open terrain while loudly splashing is possibly the worst way to start a battle. Plus, the lagoons are crisscrossed by channels of varying depth, so traveling in a straight line is never feasible.

Pepin's year-long siege had the effect of accelerating the urbanization of what would become modern Venice, as people living in communities along the edges of the lagoon took refuge on the central Realtine Islands; so called because they were a literal Rio Alto, or "High Bank" of sediment from the nearby mouths of the Sile and Piave Rivers. But in the eight and ninth centuries the modern dense city of Venice we recognize today was unrecognizable: we're still looking at a series of disconnected islands with people living in thatched roof houses facing the water and orchards and vegetable gardens out back. The City of Venice wouldn't be recognizable until at least the 10th century (and architecturally, until the 15th).

The lagoon would prove time and time again that the Venetians were untouchable: In the 9th century, when the Hungarian horde rampaged across northern Italy, it eventually set its sights on Venice. Doge Pietro Tribuno spared no time into preparing the populace for war. As Pepin had done the previous century, the Hungarians rapidly made their way up the island of Pellestrina, only to be halted at the channel of Malamocco. There they attempted to cross on coracles, which were easily rammed by the Venetian boats storming down the strait at full sail. The victory was quick and compete.

By this time, it's fairly easy to recognize that Venice was, if not a maritime power, a maritime presence. Although a far cry away from the massive state-run trading fleets of the 15th century, one chronicle attests that when St. Mark's body was stolen from its resting place in Alexandria in 832, no less than ten Venetian ships were present in the harbor. Unhampered by events on the mainland, Venetian ships carried scarce and expensive goods from the faraway east across the mediterranean, and the Venetians then floated their wares down the wide northern Italian rivers like the Adige and Po in order to to sell them to whomever happened to be on top of the greasy pole at that point in time.

With its increasing prominence in the Mediterranean trade (and here we get back to your question) soon the lagoons and the surrounding territories indeed began to experience shortages of good shipbuilding wood. However, just across the Adriatic was Istria, a heavily wooded peninsula just north of the Byzantine-claimed Dalmatian coast. Dalmatia had, by the 9th century, submitted to the Kingdom of Hungary (but not without periodic uprisings in the cities, incited by Venetian expatriate communities which would conspire to flip the whole of Dalmatia over to the Republic of Venice by the 14th century). Istria, which after Charlemagne's conquest was theoretically part of the Kingdom of Italy, also housed some urban citizens unenthusiastic about submitting to a King. By 932, the port of Capodistria swore fealty ("federata" and 'fidelitas") to the Republic in exchange for a yearly tribute of wine, and by 973 neighboring Isola follows suit. These two "Associate Cities" were enough to guarantee Venetian ship constructors an ample supply of good lumber from their surrounding area.

Little over hundred and fifty years later, repeated Venetian expeditions clearing the Istrian and Dalmatian waters of pirates in addition to increasingly favorable commercial treaties with the Byzantines giving Venetian merchants astoundingly free access to eastern goods as well as a tentative willingness of the Venetian government to dip its toes into mainland Italian affairs, led to a new expansion of Venetian territory. The city of Pola, an important administrative center of the German Empire's nominal County of Istria, was persuaded to swear fidelitas to Venice. In exchange for naval protection Pola (and Capodistria) undertook to supply the Venetian fleet with an armed galley in time of war.

Pola's adherence to the Republic did more than provide Venetian shipbuilders with a new source of lumber. Pola is situated close to marble quarries; and it was with stones from these quarries that the city of Venice would pave its streets and carve its increasingly numerous monuments. By 1150, the whole of the Istrian coast would adhere to the Republic.