Building on this question, I understand pretty clearly why forests are carbon sinks (trees grow, and there is carbon stored in soil and biomass).
What about the oceans, though? Are underwater plants the real actors here?
Check out the excellent Wikimedia picture of the carbon cycle:
All the numbers are in billions of tons of carbon: white = stored, yellow = natural flux, red = human contribution. Notice that the deep ocean stores much more accessible carbon than any other carbon cycle source, and is only surpassed by the lithosphere* in overall quantity of carbon stored on the planet. Some is stored by algae/sea plants, but the vast majority is stored as dissolved CO2.
*The lithosphere (crust and upper mantle) is not involved in the carbon cycle, and is therefore not shown in the above image.
The diagram in the answer by @Luigi does a great job describing how oceans operate as both short-term and long-term carbon sinks. Where phytoplankton can immediately uptake carbon and then upon their demise (as well as the demise of other marine organisms), the action of their sinking to the ocean floor transmits carbon to the deep ocean, where carbon is stored for decades to centuries (based on where in the ocean this occurs).
The second question you ask about underwater plants is especially interesting and an area of active research! For example, the Blue Carbon Initiative is trying to evaluate the global potential of "blue carbon ecosystems", that is coastal photosynthetic systems (i.e., Mangroves, Salt Marshes, and Seagrasses), to sequester carbon in their soils.
In addition to carbon seqeuestration, there is also the problem of ocean acidification, where the absorption of CO2 in seawater is making the ocean more acidic. Under those circumstances, both seagrasses and kelp forests are being considered as potential "ocean acidification refugia".
And, the state of California recently passed legislation to understand the role of eelgrass, a specific type of seagrass, in sequestering carbon and reducing the impacts of ocean acidification.