Yes they are stored separately, there are in shapefiles, created with the coastline checker from OSM data. The coastline checker merges all the individual natural=coastline 's to one big area. See http://wiki.openstreetmap.org/index.php/Mapnik#World_Boundaries. Before the coastline checker, VMAP data was used for the rendering of oceans.