That Brittany was founded by British emigrants in the post-Roman period is well-known. The Breton language still flourishes and shows clear links with the British languages remaining in Britain. A quick look at a map of Brittany shows, for example, many placenames beginning with 'Lan' (the same as Cornish 'Lan' or Welsh 'Llan'; meaning 'enclosed holy place'), 'Tre' (identical in Cornish and Welsh; meaning 'settlement'), or 'Ker' (same as Welsh 'Caer' or Cumbrian 'Car' as in Carlisle; meaning 'fortified place', generally descended from Latin 'castrum'). Many of the religious centres in Brittany - St Pol, Dol, St Malo, St Brieuc - were founded by Britons, generally from what is now S Wales.
That British emigrants also settled in Galicia is much less well known. Since the end of the Franco regime and a general decentralisation in Spain, many Galicians have claimed Celtic roots, to establish, for example, common traditions in folk music. But this has generally been oriented to Ireland and the Gaels rather than Britain, and largely based on the well-known Irish tradition that the Irish originally came from Spain. Much of Iberia was Celtic in the Iron Age, and the language of the Celtiberians is thought to have been Goidelic; see, for example, Jesús Rodríguez Ramos's site. If so, this would point to a link between Iberia and Ireland. However, whether Iron-Age Galicia specifically was Celtic is less certain; evidence from archaeology, written records, placenames, etc is sparse.
There are however a dozen or so placenames in Galicia beginning with 'Brit-' or 'Bret-', which may (or may not) hint at a British influence. A distinctive feature of the Galician landscape is the castros, Iron-Age hill-forts of which there are several thousand in NW Iberia (see for example paper in E-Keltoi for more info). Intriguingly, one of the finest of these is the Citania de Briteiros, now in N Portugal but in what was formerly Galicia and close to where S Martin set up his monastery at Dumio.
The best-documented link between the British and a 'Brit' placename is however Bretoña, described in a series of ecclesiastical documents from the C6 onwards. Put briefly, these document a British see, churches and a monastery (ad sedem Britonorum ecclesias que sunt intro Britones una cum monasterio Maximi) and one Mailoc, bishop of this see (Mahiloc Britonensis ecclesiae episcopus). This documentation is well summarised in a booklet Historia de Bretoña by Antonio García y García, Emeritus Professor at the Pontificia University in Salamanca, and published by the Diputación in Lugo, though unfortunately now out of print. There's a review in English on the Heroic Age website by Simon Young, a British researcher who has taken an interest in the subject. The latter has set up a website (also available here; this includes an extensive bibliography) and written a book Britonia: Camiños novos (in Galician; see review on website of the Breton-Galician twinning organisation, though 'Comme chacun sait' is stretching it a bit; 'Comme presque personne sait' would be more like it!); an item of his summarising the position appeared in History Today.
Besides these specialist works, more general works on Galicia and the British also mention Bretoña: R.A.Fletcher's study of Diego Gelmírez St James' Catapult does so and is now available online at the American LIBRO site (see Chapter 1 and search for 'brit'); a good recent summary of our knowledge of the British in general, which includes the Galician settlements, is Christopher A. Snyder's The Britons (Blackwell, 2003 - interview with author at Oxbow Books). There are quite a few Bretoña-related websites around: the Diputacion have some info in their list of municipalities; see also Pangalaica and Galicia Espallada; there is a yearly Lugnasad festival in Bretoña parish: see here and here; and there's a tradition that Maeloc's treasure is buried on the nearby mountain of Cornería (see Barreiros site) - a story that bears more than a passing resemblance to British legends.
The presence of a British settlement in Galicia, based in Bretoña where it reoccupied an existing castro, is thus well documented. We do not know when the Britons arrived, though the presence of a see in 569 and its participation in the Council at Braga implies that the community was already well established by that time. García y García states that S Martin's monastery at Dumio was organised on Celtic lines; it's tempting to speculate that this was due to the influence of the British colony - where else would a Celtic church influence have come from? Or was this founded by another British colony? Was this why the Citania was named 'Briteiros'? Though we do not know how widespread the British community at Bretoña was, the diocese appears to have been quite large and extended into what is now Asturias. Although the see was destroyed by the Moors in 716, and later moved to S Martin de Mondoñedo and in the C12 to Mondoñedo itself, references to Britons continue for several hundred years. Simon Young raises the interesting possibility of a Brythonic-speaking people in Galicia as late as the C13 - after the Liber Sancti Jacobi.
Nor is that quite the end of the British-Galician ecclesiastical links: substantial trade links between Britain and Galicia continued throughout the Middle Ages, supplemented by the transport of pilgrims to Santiago, and in 1555 a London merchant named John Dutton brought an image of the Virgin from St Paul's Cathedral (where it was in danger of being destroyed by Protestant iconoclasts) to . . . yes, Mondoñedo, where it continues to be venerated to this day, though as La Inglesa not La Britoña!
Although you would think that Galicia and Britain were too distant to matter very much to the early Church in Rome, this is far from the case. In a curious parallel between these outposts of the Roman Empire, both had charismatic church leaders whom Rome felt threatened by and declared heretical: Priscillian in Galicia and Pelagius in Britain. And when Rome decided that the Anglo-Saxons should be converted, it sent a special envoy, Augustine: Britain was obviously too important to leave to the British church. Galicia of course became one of the leading pilgrimage centres in Christendom. How deliciously ironic if, as some maintain, the shrine in fact houses the remains of the heretic Priscillian!
Though we do not know when the Britons arrived in Bretoña, there is the curious fact that the tribe to the east of Bretoña was called Albiones; a memorial stele to one Nicer Clutosi, 'Princeps Albionum', was found near Vegadeo in 1932, and is now in the Asturian Archaeological Museum in Oviedo. Albion/Albiones was also a term used by various Greek and Roman writers, including Pliny, to describe Britain and its inhabitants. It's clearly linked to Alba/Alban, the word for Scotland in modern Celtic languages, and is listed in the Celtic Lexicon of the University of Wales' Celticity Project as the Proto-Celtic root for Britain.
Archaeology tells us there was extensive trade between Iberia and the British Isles in both the Bronze and Iron Age. Whether or not Galicia was Celtic, there is archaeological evidence of prehistoric peoples from Brittany settling in Galicia. Recent genetic research too points to peoples all along the Atlantic coast from N Spain to Scandinavia being related since the Ice Age. Substantial trade between the Mediterranean, especially Phoenicia/Carthage, and Britain, especially for tin, is well documented (one theory of the origin of the word 'Britain' is that it is Phoenician Baratanak, 'land of tin'). Although the main Phoenician entrepot in Iberia was Cadiz, it's by no means impossible that traders made use of existing trade patterns between NW Iberia and Britain.
All in all, it begins to look as though it is our own time that is the aberration: links between the peoples of NW Iberia and the British Isles were much closer in prehistoric and historic times than has been the case since the C16. The old legend of the Irish originating in Spain was simply part of a much broader pattern of movement of peoples along the Atlantic edge of Europe.