This is kind of a wide-ranging question. I'll do my best with it.
The Goidelic branch of the Celtic languages consists of Irish Gaelic, Scottish Gaelic, and Manx. It appears to have differentiated in Ireland, the other branches existing due to conquest/immigration. In particular, Scottish Gaelic pretty much completely replaced the Pictish element in Scotland, starting sometime between the 3rd and 6th centuries. There was also, according to the Romans, a movement into Cornwall and Wales, but that doesn't seem to have had a lasting impact. The word Gaelic itself seems to have been an Old Welsh word for "pirate" or "raider". :-)
Here's a pitcure Wikipedia had showing the divisions of Celtic in the British Isles in the 5th Century. Green is Goidelic, Red is Brythonic, and Blue is Pictish, which eventually got replaced by Goidelic (and then Anglo-Saxon).
The earliest historical attestation I could find for Goideic:
The oldest written Goidelic language is Primitive Irish, which is attested in Ogham inscriptions up to about the 4th century. The forms of this speech are very close, and often identical, to the forms of Gaulish recorded before and during the Roman Empire. The next stage, Old Irish, is found in the margins of Latin religious manuscripts from the 6th to the 10th century
Going further back, you get your first clue here. Goidelic languages in the 4th century were not all that far removed from the Gaulish being spoken in today's France. Gaulish in turn is an Indo-European language of the Western branch. Indo-European is generally presumed to have been native to somewhere in the eastern european or west asian steppe. So presumably when the Indo-Europeans moved into Western Europe, their language became Celtic (or "Gaulish"), and when the Gauls moved into the British Isles, their languages became Goidelic in Ireland and Brythonic in England (and perhaps Pictish in Scotland).
One correction I should make here though. Galician in Spain is a language cousin to Portugese. It is a Romance language, and doesn't have any closer relation to Celtic languages than any other Romance language does. (How close is a matter of debate. It used to be popular to combine them into a sub-family. Today that idea is out of fashion).
The question was probably thinking about the Gallaeci (dang, this gets confusing), who were an ancient continental Celtic people, absorbed by the Romans, who historically had lived in the same area. They and the other Celtiberians shared their respective regions of the Iberian peninsula prior to the Roman era.
However, after the Roman Era, there was a movement of Brythonic speakers into the NW of the Iberian peninsula (along with the Brittany peninsula in France), presumably as refugees from Anglo-Saxon conquests of their territory in England. Their settlement Britonia doesn't appear to have lasted very long as a culturally distinct unit*, but it did happen.
* - Their church used the Celtic rite for about 50 years.