Punjab province in shown in at the top left of the map above in crimson.
Gypsies have Indian origins in the Punjab province (population 81 million) of Northwest India, according to multiple evidence from linguistics, autosomal DNA evidence, a rare specific genetic disease mutation, and mtDNA evidence:
The dispersion of the Roma (Gypsies) through Europe represents one of the most remarkable people movements in recent historical times. The current estimates of the total Roma population size in Europe range from 4 to 10 million, with the largest numbers concentrated in Central and South-eastern Europe. The Roma constitute a diasporic population without any reliable written records, neither historic nor genealogic. Mainly of nomadic lifestyle and with endogamous social practices, the geographically dispersed Roma populations have been socially marginalized and historically persecuted.
Linguistic, anthropological, historical and genetic evidences point out India as the origin of the Roma populations, which may have left the continent approximately between the 5th–10th centuries.
After leaving India, the Roma migration route passed through Persia, Armenia, Greece and the Slavic-speaking parts of the Balkans. The acknowledgment of the Roma establishment in the Balkan region is uniformly accepted to have taken place during the 11th and 12th centuries, where they remained for two centuries before they started spreading out to all over Europe. The dispersion throughout the continent was a very fast process since by the 15th century Roma had reached the Northern and Westernmost fringes of Europe. Indeed, historical documents testify that by the early 15th century Roma were present in Catalonia and by the end of the century they were spread all over Spain and Portugal. The most important gateway for the entrance of Roma in Iberia is believed to have been the Trans-Pyrenees route. . . .
Linguistic evidences point out to North-western India as the source of the proto-Roma population, specifically to the Indo-Aryan ethnic groups in that area. Multilocus comparison of classical genetic markers showed strong affinities of the Roma with Rajput and Punjabi populations from North-Western India. Additional genetic evidence relating the Roma populations to this geographical area comes from the study of a private mutation causing primary congenital glaucoma in the Roma which has been also described in a family belonging to the Jatt, an ethnic group of Indo-Aryan descent from the Pakistani Punjab province. . . .
The European/Middle Eastern [mtDNA] haplogroups accounted for 65% to 94% in different Roma groups, whereas the rest of the lineages belonged to haplogroup M. . . . Within haplogroup M, all lineages were of clear Asian origin except one East African M1a1 sequence found in two Portuguese Roma. . . . When the analysis was performed at state level, results pointed at Punjab state (in North-Western India) as the most probable candidate to be the ancestral homeland of the Roma mtDNA types (probability = 0.54).
While an origin in Punjab province is only 54% likely based on mtDNA evidence alone, the corroboration of that conclusion with three other lines of evidence, two genetic and one linguistic, with one of the congenital disease mutation evidence being extremely specific makes a Punjabi origin for European Roma a near certainty, solving one of the long standing grand questions of history.
The resolution of this question comes with a bitter irony. Hitler, in ordering the extermination of Gypsies in Nazi death camps in the Holocaust, in pursuit of a more pure "Aryan race" for Germany, killed the only people in Europe who were actually Aryan.
UPDATED 1-12-2011: The Y-DNA story, however, does not necessarily tell the same story, and is suggestive of origins in Orissa. Of course, one can imagine ways that founding men with roots in Orissa (perhaps a detachment of soldiers deployed away from home deprived of opportunities to return home by political events) could join women from Punjab to produce the results that we see. Support for a narrative of Eastern Indian men moving to Punjab where they take local women as wives before moving on is found here where the existance of a community of Eastern Indians who relocated to Punjab (called the Domba) is identified.
Linguistic evidence also tends to narrow the likely date of departure from India to around 1000 CE to 1030 CE, although stray historical references could push that date back to around 800 CE. The genetic data supports this general timing.