A number of recent academic papers have investigated Paleo-Asian ancestry in Asian and New World populations.
Much of the most recent research confirms the existing paradigm, or quantifies it in a manner generally in agreement with old results although with some quantitative differences.
The big headlines are that there is evidence suggestive of Paleo-Asian ancestry in indigenous South American populations of the Amazon (that does not look like modern East Asian ancestry), but not in places in between it and the Andaman Islands that are the best match to this ancestry component today. Naively, this Andaman Islands-like component appears to have arisen more than 4,000 years ago (perhaps much earlier), which is before any Asian population had the boating technology to reach South America without leaving signs of their passage along the way in settlements left over centuries. 
There is also a trace amount of Denisovan ancestry, embedded proportionately in Paleo-Asian ancestry that looks like the founding population common to Papuans and Aboriginal Australians throughout Southeast Asia, East Asia and the Americas in populations that lack the elevated Andaman Island-like ancestry. 
There is also some evidence of population structure in the founding population of the Americas that would break that population into two (or even three) parts, excluding subsequent migration.  A new study doubts previous conclusions supported by linguistics, archaeology and genetics that there was a separate Na Dene wave of migration sometime around the early Bronze Age.
There are questions over what proportion of Japanese ancestry is traceable to the Jomon with a new estimate coming in lower than previous ones (although possibly due to methodological flaws).
Yet another study demonstrates that there were at least two major into Eurasia waves of migration, an earlier one to Asia via India, and a later one with a more northern orientation. But, it notes that evidence of recent admixture in Asia obscures the older layers of population and migration history that can be discerned from genetic data in Asia.
All of this new data goes into the cauldron as we try to piece together a comprehensive narrative of the modern human settlement of the region and the interactions of these wave of migration with the hominins archaic or otherwise who came before them, that can explain all of the evidence in a persuasive manner.
That task if left for a latter post. This post looks at the data on Jomon ancestry, and lays some of the related groundwork, without plunging into a full analysis of the big questions set forth above.
By Paleo-Asians, I mean to include modern humans from their earliest arrival in Asia in the Upper Paleolithic era (or, at least, post-Toba explosion ca. 75,000 years ago), the founding population of North America and South America, the founding populations of Papua New Guinea and Australia, the Jomon people of Japan, the Andaman Islanders, the populations commonly classified as Paleo-Siberian, and any other modern humans who arrived roughly speaking, prior to the Mesolithic era that immediately preceded the Neolithic Revolution (i.e. populations that arrived more than ca. 10,000 or so years ago), many of whom no longer exist as distinct populations, as well as modern humans who have substantial ancestry from these early arriving populations.
In contrast, I intend to exclude modern human populations that expanded during, after, or immediately prior to the Neolithic revolution in the area where they were located (outside Papua New Guinea or the Americas). For example, populations that arrived in Siberia only after the Neolithic revolution, like the Tocharians and the Indo-Iranians and the Russians, are not Paleo-Asians Neither are the Han Chinese, the rice farming cultures of South China and Southeast Asia, the Austronesians after their ethnogenesis (in each case),
I also intend to exclude archaic hominins, although genetic traces of admixture between Paleo-Asians and archaic hominins are critical to working of the prehistoric story of the Paleo-Asians.
The term Asia, as used in this post does not include West Asia or Southwest Asia, and is also sometimes used in the sense of East Eurasian, or in the sense of East Eurasian and Native American.
Archaic Hominins and Modern Humans Outside Africa
It is widely acknowledged that the first hominin in Asia, first appearing around 1,800,000 years ago, was Homo Erectus, for which type fossils are found on the island of Java in Indonesia (Java Man), and in the vicinity of Peking, China. (Peking Man). There is no indication in the archaeological record that Homo Erectus ever made it to Japan, the Philippines, the island of New Guinea, Australia, Oceania, or the Americas. The most recent Homo Erectus remains that are reliably dated and classified is 250,000 years old. Another specimen from China, Dali Man is dated to 209,000 years ago +/- 23,000 years, but the classification of the specimen as Homo Erectus is not as definitive.
There is virtually no direct archaeological evidence of hominins within the range of Asian Homo Erectus in the time from from about 200,000 years ago to the time of the Toba eruption.
Homo Erectus was not limited to Asia. For example, it was also found in the Caucasus Mountains that form one of the boundaries of Europe. Homo Erectus in Asia (i.e. east of India) do not show any change in their associated tools in the archaeological record. Non-Asian Homo Erectus, in contrast, show a single major advance in their tool kit in the archaeological record.
No ancient DNA has been obtained from this species.
Denisovans and Homo heidelbergensis
Ancient DNA from a hominin species, known as Denisovans, has been recovered from a 41,000 year a fragment of a finger bone and two teeth in a cave in Denisova, Siberia. But, these were found without other sufficient accompanying bones to make an archaeological classification of the species relative to archaic hominins who are known only through their skeletal remains and characteristic tool kits.
As noted below, there is also a species, whose existence is disputed, called Homo heidelbergensis found in Europe after the earliest Homo Erectus sites, but before Neanderthals appeared, and are usually presumed to have evolved from Homo Erectus. Before ancient DNA was available, Homo heidelbergensis was commonly believed to be intermediate species between the two archaic hominin species, but the picture is now more complicated. Homo heidelbergensis disappear from the fossil record around the time that Neanderthals appear and no examples of Homo heidelbergensis remains have been found in the area where Asian Homo Erectus is found.
Wikipedia notes that (references renumbered to correspond to the order in this blog post):
Analysis of the mitochondrial DNA (mtDNA) of the finger bone showed it to be genetically distinct from the mtDNAs of Neanderthals and modern humans. Subsequent study of the nuclear genome from this specimen suggests that this group shares a common origin with Neanderthals, that they ranged from Siberia to Southeast Asia, and that they lived among and interbred with the ancestors of some present-day modern humans, with about 3% to 5% of the DNA of Melanesians and Aboriginal Australians deriving from Denisovans. DNA discovered in Spain suggests that Denisovans at some point resided in Western Europe, where Neanderthals were thought to be the only inhabitants. A comparison with the genome of a Neanderthal from the same cave revealed significant local interbreeding, with local Neanderthal DNA representing 17% of the Denisovan genome, while evidence was also detected of interbreeding with an as yet unidentified ancient human lineage. . . . In 2013, mitochondrial DNA from a 400,000-year-old hominin femur bone from Spain, which had been seen as either Neanderthal or Homo heidelbergensis, was found to be closer to Denisovan mtDNA than to Neanderthal mtDNA.Comparison of this ancient DNA to whole genomes of modern humans reveals that there is significant Denisovan admixture in modern humans from the Flores side of the Wallace line and beyond, including Aboriginal Australians (3-5%), indigenous Papuans (3-5%), and Oceanian populations that had admixed with any of the foregoing. In all of these populations, Denisovan admixture is closely correlated with Papuan ancestry, but not with Australian Aboriginal ancestry (which is basically absent). It is also found at elevated levels in Philippino Negrito populations. The fact that modern humans with Densiovan admixture are found so far from Siberia is a mystery.
The Denisovan sample itself shows a 17% introgression of autosomal DNA from a Neanderthal population for which ancient DNA from the same case, several thousand years later in a different archaeological stratum was recovered.
Remains of a small hominin colloqially named after J.R.R. Tolkein's Hobbits whom they resemble in size and build, were present on the island of Flores at the same time that modern humans were present there. They have been hypothesized as a possible candidate for Denisovan admixture because they were an archaic homin specifies known to be in the right place at the right time to account for most observed Denisovan admixture in modern humans. No ancient DNA has been obtained from this species.
Neanderthals are found in the Middle East, West Asia, Europe (although not in environments as frigid as the most extreme environments where hunter-gatherer modern humans lived), in Northern Asia as far east as the Denivosan cave in Siberia and the Altai Mountains, and in South Asia as far as Pakistan or perhaps slightly further east, but not close to the eastern boundary of India. They went extinct a little less than 30,000 years ago. There are multiple good ancient DNA samples from Neanderthals.
All existing modern humans with ancestry from outside of Africa have Neanderthal ancestry, as do Africans who have back-migrated Eurasian ancestry in proportion to that ancestry (e.g. many North Africans and many East Africans). Neanderthal ancestry in living modern humans tends to be slightly higher in Asians than in Europeans and averages 1-3% of their ancestry. Individuals who have Denisovan ancestry also have typical amounts of non-African Neanderthal admixture.
As noted above, the available Denisovans DNA samples from Siberia also have substantial Neanderthal admixture.
The oldest modern human remains (other than the controversial Dali Man claim from China) are Omo 1 and Omo 2 from Ethiopia which are dated to 190,000 years ago and were discovered in 1967. The oldest modern human remains outside of Africa are Qafzeh 6, IX and VI which are dated to 90,000 to 100,000 years old, and Skhul V and IX dated to 80,000 to 120,000 years ago, each of which is in Israel. Archaeological relics support an earlier out of Africa and into Arabia date as early as about 130,000 years ago.
No modern human remains or archaelogical relics associated with modern humans have been found in Asia to the east of India in prior to the massive eruption of the Toba volcano ca. 66,000-77,000 years ago. But, within a few thousand years after the Toba eruption, modern human remains are found in Southeast Asia and Australia. There is archaeological evidence of modern humans in Southern India both before and after the Toba eruption that tends to show that a single archaeological culture spanned that event.
One Paleo-Asian population is the Jomon people whose closest surviving descendants are the Ainu people of modern Japan.
A paper analyzed at Bernard's blog examines the Paleo-Asian substrate in linguistically Japonic or Ainu populations using genetic data from "classic markers, mitochondrial DNAs, Y chromosomes and genome-wide single-nucleotide polymorphisms (SNPs)."
Japan was first inhabited by hominins about 30,000 years ago, and about 16,000 years ago, an archaeological culture known as the Jomon arose either due either to new migration or to in situ cultural development of Japan's existing inhabitants. The timing is after the Last Glacial Maximum (LGM), ca. 20,000 years before present, at which Japan was at its most easily accessible in modern human times due to low sea levels, at around the time that the wild fluctuation in climate the followed the LGM started to stabilize somewhat.
The Jomon were fishermen who also hunted and gathered food. The sedentary lifestyle associate with fishing based subsistence allowed the Jomon to become the first culture to develop pottery. In contrast, pottery did not appear in the Levant until sometime in the vicinity of 6200 BCE to 5500 BCE, even though the herding and farming and towns (Jericho) arose in the Levant as part of the pre-pottery Neolithic period starting around 8500 BCE to 8000 BCE and even though sedentary fishermen who also hunted and gathered and engaged in proto-farming of wild type crops were present in the Levant as early as 23,000 years ago. There is even suggestive evidence that implies that all pottery in Eurasia is derived from the Jomon invention of that craft. According to :
The upper Paleolithic populations, i.e. Jomon, reached Japan 30,000 years ago from somewhere in Asia when the present Japanese Islands were connected to the continent. The separation of Japanese archipelago from the continent led to a long period (∼13,000 – 2,300 years B.P) of isolation and independent evolution of Jomon. The patterns of intraregional craniofacial diversity in Japan suggest little effect on the genetic structure of the Jomon from long-term gene flow stemming from an outside source during the isolation. The isolation was ended by large-scale influxes of immigrants, known as Yayoi, carrying rice farming technology and metal tools via the Korean Peninsula. The immigration began around 2,300 years B.P. and continued for the subsequent 1,000 years. Based on linguistic studies, it is suggested that the immigrants were likely from Northern China, but not a branch of proto-Korean.Thus, around 1300 BCE, a rice farming, horse riding, warrior dominated people called the Yayoi from mainland East Asia, arrives in Japan oversea from what is now South Korea, and become a superstrate population which integrates substantial proportions of Jomon people into their society, but incorporates almost no Jomon linguistic elements into what will become the Jomon language.
The timeline in Okinawa is potentially consistent in broad brush strokes with the rest of Japan (the oldest human remains are 32,000 years old), but the archaeological record is thinner (there is no archaeological record indicating a human presence of any kind from 18,000 to 6,000 years ago), rice farming arrives only many centuries after the Yayoi do, and earliest historical mention of Okinawa in surviving written documents is from 607 CE.
The Yayoi spread as far South as the Ruyukyu island in the South. Japan has four major islands, Hokkaido, Honshu, Shikoku and Kyushu, but initially the Yayoi control only Kyushu, Shikoku and Southern Honshu until around 1000 CE. Northern Honshu and Hokkaido are home to a population related linguistically and genetically to the modern Ainu indigenous people of Japan who are descendants of the Northern-most of the Jomon people.
Previous Y-DNA and mtDNA data on Japanese population genetics can be summed up as follows (from ):
Genetic studies on Y-chromosome and mitochondrial haplogroups disclosed more details about origins of modern Japanese. In Japanese, about 51.8% of paternal lineages belong to haplogroup O6, and mostly the subgroups O3 and O2b, both of which were frequently observed in mainland populations of East Asia, such as Han Chinese and Korean. Another Y haplogroup, D2, making up 35% of the Japanese male lineages, could only be found in Japan. The haplogroups D1, D3, and D*, the closest relatives of D2, are scattered around very specific regions of Asia, such as the Andaman Islands, Indonesia, Southwest China, and Tibet. In addition, C1 is the other haplogroup unique to Japan. It was therefore speculated that haplogroups D2 and O may represent Jomon and Yayoi migrants, respectively.
However, no mitochondrial haplotypes, except M7a, that shows significant difference in distribution between modern Japanese and mainlanders. Interestingly, a recent study of genome-wide SNPs showed that 7,003 Japanese individuals could be assigned to two differentiated clusters, Hondo and Ryukyu, further supporting the notion that modern Japanese may be descendent of the admixture of two different components.Previous autosomal DNA studies of the Ainu and Ryukyu confirm that they are a tightly clustered group relative to other populations for which autosomal DNA is available. This supports the inference that both populations have predominantly Jomon and Yayoi ancestry, albeit perhaps in slightly different proportions with minor additional elements in one or both of these populations.
This most recent study analyzes whole genomes from Ainu, Ryukyuans and Mainland Japanese populations, using Han Chinese and Korean populations as outgroups. It finds that:
(1) the Ainu are genetically different from Mainland Japanese living in Tohoku, the northern part of Honshu Island; (2) using Ainu as descendants of the Jomon people and continental Asians (Han Chinese, Koreans) as descendants of Yayoi people, the proportion of Jomon genetic component in Mainland Japanese was ~18% and ~28% in Ryukyuans; (3) the time since admixture for Mainland Japanese ranged from 55 to 58 generations ago [1,450 years], and 43 to 44 generations ago for the Ryukyuans [1,100 years], depending on the number of Ainu individuals with varying rates of recent admixture with Mainland Japanese; (4) estimated haplotypes of some Ainu individuals suggested relatively long-term admixture with Mainland Japanese; and (5) highly differentiated genomic regions between Ainu and Mainland Japanese included EDAR and COL7A1 gene regions, which were shown to influence macroscopic phenotypes.The first result is to be expected, both because of mainland East Asian admixture in the people of Northern Honshu in the last 1,000 years, and because of a likely North to South cline in the non-East Asian genetics of the Japanese people that probably reflects more Northeast Asian (i.e. basically Siberian) admixture in the north.
Bernard appropriately notes that the date of admixture estimates in the study can be considered as lower bounds knowing that the rolloff program assumes a single genetic mixing event and the most recent estimates in the case of several events. The rolloff dates are consistent with the end points of a roughly one thousand year period of admixture from the first arrival of the Yayoi in Central Japan and Okinawa respectively.
Bernard also notes that some of the genes with known phenotypic effect distinguishing the Ainu and Central Japanese are genes associated with facial structure of European (and PAX3 COL7A1) and the morphology of the teeth and hair of East Asians (EDAR), which is unsurprising given the different physical appearance of approximately pureblooded Ainu people and Central Japanese people, with the Ainu looking much more similar to Europeans despite not having strong genetic ties to them.
The fact that Ryukyuans appear to have more Jomon ancestry (28%) than Central Japanese people (18%) is interesting, because Ryukyuan is actually closer to the Yayoi proto-language than the principal Japanese language. Realistically, in both cases, the Jomon language(s) was overcome by the Yayoi language, but Ryukyuan received less subsequent linguistic influence from China, Siberia and global trade. These estimates are conservative. A 2012 study that similarly used the whole genomes of modern populations to estimate the pre-Yayoi population's contribution to the autosomal DNA of the Japanese people using a different statistical approach concluded that "the genetic contributions of Jomon, the Paleolithic contingent in Japanese, are 54.3∼62.3% in Ryukyuans and 23.1∼39.5% in mainland Japanese, respectively. Utilizing inferred allele frequencies of the Jomon population, we further showed the Paleolithic contingent in Japanese had a Northeast Asia origin." Both studies agree that the Jomon contribution is higher in the Ryukyuans than in the Central Japanese people, and concludes the the relative proportions are about the same, but finds that the absolute proportions are about twice as high, and are more in line with the roughly 38% that we would expect for Central Japanese individual from the combined Y-DNA and mtDNA data, all other things being equal. (It is perfectly possible for the autosomal ancestry percentage attributable to an ancestral population to differ greatly from the average of the percentage of Y-DNA from that population and the percentage of mtDNA from that population; but the assumptions necessary to cause the autosomal ancestry percentage to be close to the average of the Y-DNA percentage and mtDNA percentage aren't particularly stringent and are a reasonable expected value unless one knows something special about the nature of the admixture event between the different admixed populations.)
As I noted in a January 24, 2015 post discussing Japanese and Korean linguistic features reported in the WALS database, Wikipedia, and certain other sources, ejective glottal consonants are found in Korean and they are also found in the North Ryikyuan languages (such as the language of Okinawa) which, "in general, preserve features found in Old Japanese that are absent in modern Japanese. The fact that the North, rather than the South Ryukyuan languages have these consonants also suggests (in accord with other lines of evidence regarding the prehistory and ancient history of these islands) that glottal consonants in the North Ryukyuan likely derive from the language spoken by the Yayoi migrants to Japan, rather than an areal influence from the island of Formosa (Taiwan) or Southern China, of some kind.
The percentage is lower than might have been expected from the fact that about 43% of Japanese Y-DNA and about a third of Japanese mtDNA is attributable to Jomon sources. More fundamentally, it is disappointing that the study used an Ainu proxy, when ancient Jomon automsomal DNA is apparently available.
 Pengfei Qin and Mark Stoneking, "Denisovan Ancestry in East Eurasian and Native American Populations" (April 3, 2015) (pre-print).
 Jinam, et al., "Unique characteristics of the Ainu population in Northern Japan", Journal of Human Genetics (July 16, 2015).
 Tassi, et al., "Early modern human dispersal from Africa: genomic evidence for multiple waves of migration" (July 20, 2015) (pre-print).
 Skoglund et. al., "Genetic evidence for two founding populations of the Americas" Nature (July 21, 2015).
 Raghavan, et al., "Genomic evidence for the Pleistocene and recent population history of Native Americans" Science (July 21, 2015).
 Krause, et al., "The complete mitochondrial DNA genome of an unknown hominin from southern Siberia" Nature 464 (7290): 894-897 (April 8, 2010).
 "About 3% to 5% of the DNA of people from Melanesia (islands in the southwest Pacific Ocean), Australia and New Guinea as well as aboriginal people from the Philippines comes from the Denisovans." Oldest human DNA found in Spain -- CNN reporter Elizabeth Landau's interview of Svante Paabo, a co-author of , accessdate= (December 10, 2013).
 Pennisi, Elizabeth, "More Genomes from Denisova Cave Show Mixing of Early Human Groups", Science 340 (6134): 799 (2013).
 Callaway, Ewan, "Hominin DNA baffles experts". Nature (journal) 504: 16–17 (5 December 2013).
 Samuel Bowles and Jung-Kyoo Choi, "Coevolution of farming and private property during the early Holocene", PNAS (July 16, 2012).
 Snir, et al., "The Origin of Cultivation and Proto-Weeds, Long Before Neolithic Farming" PLOS ONE (July 22, 2015).
 Jordan, Zvelebil, "Ceramics Before Farming: The Dispersal of Pottery Among Prehistoric Eurasia Hunter-Gatherers" Left Coast Press (2009).
 Yungang He et al., Paleolithic Contingent in Modern Japanese: Estimation and Inference using Genome-wide Data, Scientific Reports (April 5, 2012).
 Japanese Archipelago Human Population Genetic Consortium, "The history of human populations in the Japanese Archipelago inferred from genome-wide SNP data with a special reference to the Ainu and the Ryukyuan populations" 57 Journal of Human Genetics 787-795 (December 2012).
 Hideaki Hanzawa-Kiriyama, "Nuclear Genome Analysis of Ancient Japanese Archipelago Humans" (January 15, 2015) (symposium paper).