Humans continue to emit vast amounts of carbon dioxide (CO2) into the atmosphere. Emissions reductions alone will be insufficient to remain below an average 2˚C of warming, and we will need to remove CO2 from the atmosphere at the scale of gigatonnes per year by the end of the century. Biomass-based CO2 removal (CDR) leverages photosynthesis to convert atmospheric CO2 to organic carbon that can be sequestered. Potential approaches are diverse, ranging from macroalgae cultivation with sinking to the deposition of agricultural wastes in deep anoxic brines. Rigorous and consistent regulation is needed to track how much carbon proposed projects will store and assess potential impacts to marine ecosystems. However, there is often a mismatch between the need to predict global-scale impacts over hundreds to thousands of years and the types of data typically used in environmental monitoring. To help fill this gap, we provide a five-phase framework to structure monitoring, reporting, and verification (MRV) and support responsible decision-making about biomass-based CDR with marine storage by regulators, developers, investors, verifiers, and policymakers.