My Dear Mr. Duk:
I think having a 1 byte/cell tag may well be worth the memory hit. I still have vague fantasies about an object oriented approach where pieces and cities reside in continent containers and inherit attributes or receive messages based in part on what continent they reside in. Such location tags may prove indispensible for implementing stuff like that. (I think you would need *at least* 6 bits to allow for a 64 island archipelago; probably a full 8-bit byte makes the most sense.)
I do think, though, that every speck of land on the same continuous land mass (Eurasia) should wind up with the same ID tag. As proto-clumps collide, a table could be created showing which proto-ID tags now reside on the same land mass. You could then either A) make an additional pass through the finished cells updating continent ID tags, or B) keep the original tags in place but always filter them through the table in a way that was transparent to the user:
A) contID(x,y) = tag(x,y)
B) contID(x,y) = lookupTable(tag(x,y))
Will players ever be able to divide continents by constructing a Panama Canal or even establishing an arbitrary 42nd parallel-style demarcation line? If so, option A would be preferred bacause in such cases continent ID would no longer flow directly from proto-clump ID.
I also think we may eventually want some additional information attached to each cell. Maybe 2 or 3 bits could be set aside for an openland / mountain / forest / swamp / river / road kind of identifier. If we ever get into *serious* continent rendering, we may want elevation data as well (which could arise naturally from our existing generation algorithm). It's conceivable that political boundaries might come into play someday (color-coded territories within continents).
As for the oceans, I wouldn't worry about that just yet. It's not clear that there's any reasonable way of dividing a continuous ocean (other than just whacking it up along longitude lines) or any compelling reason to care.
Yours in haste,