My answer deals exclusively with "early on," which I take to mean "at an early stage of a lengthy event or experience." Used in this sense, "early on" is very common today in both the United States and the UK, to judge from a Google Books Search; but it originated in British English and didn't become common in U.S. English until, at the earliest, the 1970s. I tried to find (through Google Books searches) the earliest usage of "early on" as a stand-alone phrase in British and U.S. English.
Between 1879 and 1969 all of the results in a Google Books search for "early on" as a stand-alone expression are from writings by British or British commonwealth authors. Here are the first five of dozens such occurrences during this 90-year period.
From John C Bucknill & Daniel H. Tuke, A Manual of Psychological Medicine, Containing the Lunacy Laws, ... (1879):
(b.) Early on, exaggerated notions or paroxysmal excitement with strange demeanour, and, rarely, dementia. Finally, dementia, with fitful outbursts of excitement. Patient's self-satisfaction replaced by morose or distressed feelings, and these by obliteration of emotional life. Foul and destructive habits. Motor paresis comparatively slight early on.
This is an especially interesting first occurrence because it appears in a section where the authors are summarizing another author's "five varieties of General Paralysis, pathologically and clinically," and seek to "present the symptoms to the reader in as condensed a form as possible," as the telegraphic style of the excerpt indicates. Presumably the longer form of the idea would be something like "At an early stage on the course of the condition's progress toward paralysis [or whatever]." The significant thing about the author's presentation of the information here is that they had no doubt that readers would understand the sense of the short form "early on"; indeed, they liked it enough to use it twice in a single paragraph.
From "Gordon-Bennett Race History" in The Motor, volume 5 (June 20, 1904):
Of the twelve competitors, half a dozen were put out of the running early on, but out of the remaining six it was impossible until quite near the end of the race to pick the winner. ... England was singularly unfortunate in losing, early on, the services of Jarrott and Stocks, who were victims of accidents which they could neither have foreseen nor prevented;
From J. Wilfrid Jackson, "An Attempt to Breed from a Sinistral Helix Pomatia" (read as a paper on December 13, 1905), in Journal of Conchology, volume 11 (October 1906):
From this date [June 18, 1904] the snails became very inactive, often spending weeks at a stretch suspended from the cover-glass of the tank by a thin film of white mucous round the mouth of the shell. One or other of them would occasionally crawl round tank, and once I noticed S. had turned back its head, and was gnawing the lip of its shell, in the same manner as I had seen D. doing early on in the year.
From Jeffery E. Marston, Side Issues (1920):
She organized a Relief House for refugees from the battlefields and tended the sick. Quite early on she had been obliged to dispense with her servant and undertake all the housework herself. But with all her activities she could not fill her time as the months crawled slowly by.
From John Galsworthy, Loyalties, act 2, scene 2 (1922):
Margaret: Gracious! Wives are at a disadvantage, especially early on. You've never hunted with him, my dear. I have. He takes more sudden decisions than any man I ever knew.
Although "early on" continued to appear in British writing, with increasing frequency, from 1920 forward, its first appearance in a clearly U.S. English context (that is, in a book or article written by a non-British author and published in the United States with U.S. spelling conventions, to avoid counting British English reprints) was in 1970. I find this astonishing, since I grew up in the United States and was in high school in 1970, and yet don't remember a time when "early on" wasn't used in the stand-alone way that the OP asks about. The usage seems perfectly natural to me. Anyway, here is the first clearcut instance I could find of the term in a purely U.S. context.
From Garry Wills, Nixon Agonistes (1970):
Nixon made another important convert early on — Bert Andrews, chief of the Herald Tribune's Washington bureau. Andrews had just won a Pulitzer Prize for reporting the inequities of security-clearance; yet Nixon, using his intense homework, convinced him, too, that [Alger] Hiss was lying, and had his help all through the investigation.
This quotation from Garry Wills's book may have appeared (in slightly different wording but with the usage of "early on" unchanged) in Esquire magazine in 1968 as part of a shorter article on Nixon by Wills.
I haven't done comparable research on "later on" as a stand-alone term, but it appears to have come into use much earlier than "early on," both in Britain (by 1823) and in the United States (by 1886).