My question is, what good ways are there store/sink coal? Just sinking large quantities of coal in the oceans is probably be a bad idea, and can have disastrous side effects. So what is known in this direction?
You are correct, buying coal and trying to sink it into oceans is a bad idea.
Your other idea, to leave coal in the ground as nature created it, unmined, is the best idea.
First of all, leaving coal in the ground does not cost anything. To mine coal and then transport it to an ocean location and dump it costs money. To rehabilitate the mine site afterwards also costs money. This money would be better spent on other things.
Secondly, by mining coal and trying to sink it in oceans environmental damage has already occurred. Some open pit mining equipment uses diesel as an energy source. Other mining equipment is powered by electricity. If the electricity used to power the mining equipment is generated by burning coal, or even natural gas, carbon dioxide and carbon monoxide will have been added to the atmosphere.
The fact that the mine would exist means that equipment must be made to be used by the mine. The mining of the metal ores - iron for the body, copper for the electric cables, nickel and chromium for the manufacturing of steel - their processing, smelting and manufacture of equipment requires energy and produces carbon dioxide and has other negative environmental impacts. It would be better to use such resources to produce electric vehicles to be used for other purposes.
Thirdly, coal generally has a specific gravity between 1.2 and 1.5 and depending on conditions, sea water has a specific gravity between 1.028 and 1.071. Because these values are very similar sinking coal is not a straight forward as sinking iron ore or steel. If coal is largely free of contaminating ash it will float on water.