I have been trying to find enough mtDNA data to compare the distribution of mitochondrial haplogroups with Y-DNA haplogroups. Here is what I have deducted so far (not certain, but likely).
Mesolithic Europe
Following the end of the last Ice Age, European hunter-gatherers recolonised the continent from the Ice Age refugia in southern Europe. Most Mesolithic Europeans would have belonged to Y-haplogroup I. This included I*, pre-I1, I1, I2*, I2a*, I2a2, but the most widespread appears to have been I2a1, which was found in most parts of Europe. Northeast Europeans would have belonged mostly to haplogroup R1a. Other minor male lineages were certainly also present in parts of Europe, notably haplogroup A1a, C-V20, F-P96 and possibly even Q1a and R1b1* (P25).
The maternal lineages of Mesolithic Europeans appears to have been predominantly U4 and U5, but also included several H subclades (H1, H3, H17), T, U2 and V. The presence of mt-haplogroups I and W is likely but hasn't been confirmed yet.
Based on the modern distribution, haplogroups H6, H10 and H11 might well have Mesolithic/Palaeolithic European origins.
There seem to have been several Palaeolithic and/or Mesolithic migrations from Northwest Africa to Iberia. The oldest might have brought West African haplogroup A1a and A1a1a to Western and Northern Europe during the Palaeolithic. A1a has been found in modern populations as far north as Ireland, Scotland, Scandinavia and Finland. E-M81 probably crossed the Gibraltar Straits some time during the Mesolithic and settled around most of Iberia, probably expanding into the rest of Western Europe during the Neolithic period (Megalithic and Bell Beaker cultures). The presence of African maternal lineages (L2, L3 and possibly L1b1) has been attested in Neolithic Iberia. Northwest Africans would also have brought U6 and possibly HV0/V lineages to Europe.
A small percentage of sub-Saharan African admixture has been identified in Late Mesolithic Swedes from the Pitted Ware culture (2800-2000 BCE), which would imply that A1a was already present in northern Europe at the time. Another Mesolithic sample from Loschbour in Luxembourg had dark hair and considerably darker skin than modern Europeans.
Neolithic Europe
Agriculture first developed in the Levant, then spread to Anatolia, Greece, the Balkans, Italy, Central and Eastern Europe. These Neolithic farmers were confirmed to have belonged to Y-DNA haplogroups E1b1b and G2a, but probably also included a minority of J1, J2 and T lineages.
Hundreds of Neolithic samples from all over Europe (but especially Central Europe and Iberia) have been tested. The new lineages brought by these Near Eastern immigrants included haplogroups HV, J1, J2, K1, K2, N*, N1, T1a, T2b, T2c, T2e, T2f, U3, W, X1, X2, and many subclades of H (including H2, H5, H7, H13 and H20). H4, H8 and H9 seem to have originated in the Near East as well, although no Neolithic sample has been identified in Europe yet.
However, due to the proximity of the Caucasus from the Indo-European homeland, many of these haplogroups were almost certainly also transported by the Indo-Europeans themselves, notably H5, K1a, T2b, U3, W and X2.
The Indo-Europeans
The origin of the Indo-Europeans lies in the Pontic-Caspian steppe with (R1a) tribes to the north (forest-steppe and tundra) and (R1b) tribes to the south (open steppe) during the Chalcolithic and Bronze Age. Their migration both westward to Europe and south-eastward to Central and South Asia makes it easy to guess which mtDNA haplogroups they carried (=> see also Identifying the original Indo-European mtDNA from isolated settlements). The best matches for R1a are H6, I, U2, U4, U5, and W.
The R1b branch would have originated in eastern Anatolia and/or northern Mesopotamia/Syria during the Early Neolithic period, where they probably domesticated cattle and became primarily cattle herders. Then would have crossed the Caucasus to the Pontic Steppe in search for pasture for their cattle, where they mixed to some extent with southern R1a tribes. The maternal lineages of these Near Eastern R1b people would have included haplogroups H5a, I, K1a4, T2b, U3 and X2.
H4 has not been found in Europe before the Late Chalcolithic (Corded Ware) and Bronze Age (Unetice) and might have been brought by the Indo-Europeans.
Haplogroup V has never been found in prehistoric sites in Northeast Europe, nor in any Indo-European burial in the Eurasian steppe or Central Asia. It is nevertheless present in every part of Europe nowadays. Its frequency is higher than the European average in north-western Russia (> 5%), and peaks among the Sami (> 30%). Haplogroup V has also been found in most Uralic and Altaic populations across North Asia, and at trace frequencies as far as Korea and Japan. Therefore it is likely that the presence haplogroup V in Eastern Europe is related to the diffusion of Ural-Altaic populations and of Y-haplogroup N, rather than to the Indo-Europeans.