Mangrove Madness & Floating Islands:
Is your entire planet Ocean, or are there islands? Mangroves are a source of wood that is intimately tied to the sea. While it is not DEEP sea, many species are dependent on mangrove salt-water "swamps" for critical parts of their life cycles. It would likely fill the role you are looking for, allowing a sea-faring species access to wood, and might also provide an intermediary environment where sea and land species might come together in either competition or cooperation.
The problem with wood is that most aquatic plants don't find it necessary to support great weight against gravity, or have a reason to anchor resistant structures against the power of the currents, so buoyancy is the simple solution to keep a plant up. If you don't have islands, perhaps there were once islands, and there is wood preserved under the sea. My understanding is that wood is sometimes stockpiled in deep cold water to preserve it until needed. So some might be legacy wood.
A fun alternative might be to have a floating tree ecology. Ancient trees got around extinction by forming a floating platform of interconnected trees, almost like a grown ship. Perhaps some land animals or bird species take advantage of these structures to live on or lay eggs. There are certainly species of birds today that essentially never land and fly over the sea for months at a time unless laying eggs. The guano from the birds provides nutrients for the trees and carries seeds for sub-species of plants on the island. I imagine a species of Jelly fish that lives by hanging off the bottom, pulling up fish and other creatures to eat amidst the roots and providing a nutrient-rich supply of remains for the trees (plus protection from predators who might eat their roots), while the trees provide a home and safe haven for the jelly fish. The trees might have a distillation method to produce fresh water if desired (although over time they would likely tolerate salt better and better, but this could help support the floating island biome).
The jelly fish and surface environment would mean your people could get wood, but you can make that as challenging for them as you want. It could be common, or a rare and valuable commodity.