Normal Procedures: Airspace
U.S. Aeronautical Information Manual Definition
[AIM, Pilot Controller Glossary] OCEANIC AIRSPACE− Airspace over the oceans of the world, considered international airspace, where oceanic separation and procedures per the International Civil Aviation Organization are applied. Responsibility for the provisions of air traffic control service in this airspace is delegated to various countries, based generally upon geographic proximity and the availability of the required resources.
If you comb through the ICAO regulations, you come up only with this:
[ICAO Doc 9426, Part II, §4, Chapter 1, ¶1.1] Oceanic flights are conducted in airspace where no sovereign rights are exercised and where normally, in that airspace, more than one State is concerned with the provision of ATS.
So oceanic airspace begins where a State's airspace ends. But what constitutes a State's airspace?
Territory of a State
[Convention on International Civil Aviation, Article 2] For the purposes of this Convention the territory of a State shall be deemed to be the land areas and territorial waters adjacent thereto under the sovereignty, suzerainty, protection or mandate of such State.
Suzerainty: a sovereign or state having some control over another state that is internally autonomous.
So a State's territory includes its land areas and adjacent territorial waters. But what are territorial waters?
[United Nations Convention on the Law of the Sea, §2, Article 3, Breadth of the territorial sea] Every State has the right to establish the breadth of its territorial sea up to a limit not exceeding 12 nautical miles, measured from baselines determined in accordance with this Convention.
Of course not every signatory has agreed to this and many claim less and many claim more. But generally speaking, the answer is 12 nm from land. From this we can conclude that oceanic airspace normally begins 12 nm from the borders of States bordering the oceans.
Aeronautical Information Manual
ICAO Doc 9426 - Air Traffic Services Planning Manual, International Civil Aviation Organization, First (Provisional) Edition, 1984