Specifically concerning Irish, Scottish Gaelic, and Welsh—how did these spellings come to be? With contact from the Romans, Anglo-Saxons, Norse, and Normans over time, I would have thought these languages would develop a written language with less strange (sometimes seemingly nonsensical) lettering choices. Since many of these sounds already exist in the Latin alphabet, what influenced them to adopt such odd spellings?
The use of the 'h' to represent a séimhiú (the lenition of a consonant) is relatively new. Traditionally Irish was written in Gaelic script (which some enthusiasts still use) which, while still clearly based on the Roman alphabet, is different enough from regular letters to take a while to get used to. Traditional Gaelic script does not use the 'h's, it instead uses a little dot above the consonant in question. Irish went through a spelling reform in the late 1940s and a move to using modern script happened more or less at around the same time - the letter 'h' was a convenient option to replace the dot. To consider this nonsensical, if I may, is somewhat anglo-centric. More on the 'h' later.
This story was written down as part of the 1931 Schools' Folklore Collection. (A fascinating project in itself, but somewhat outwith the scope of this question). You can see several instances of the use of little dots (the dot is called a buailte) on the first line. For comparison, there is a transcription (using the 'h's and modern lettering) on the right hand side. There are many other examples (and many English-language texts also) if you have a browse around the website.
This link should take you to an Old Irish manuscript (circa 14C). I cannot understand it (it is significantly different from modern Irish), but you can see that, to complicate matters, some of the 'dots' look like little 'h's - the sound mutation involved is sometimes described as a 'softening' of the consonant, but is mostly more of an 'aspiration', a breathing-through of the letter, so using a little 'h' actually kinda makes sense.