Look at the wiki article, most of the nuclear materials dumped were solid low level waste. That sounds like it can stay on the bottom of the ocean just fine.

I do not know where most people get this mental image of dumping "barrels of waste" - maybe from movies of something. I will admit this is what I imagined in my mind, but it seems not to conform with reality.