The Northwest of Scotland has a common linkage to Norway in that both are the remains of the once-mightly Caledonide chain of mountains. This was before the Atlantic Ocean opened up, so other fragments of the Caledonides are to be found in Greenland and Eastern North America. See for example the diagrams found in Haakon's website:
http://folk.uib.no/nglhe/caledonides.html
The Caledonides have a long and complex history, far too long to summarize here. Also, there has been "a lot of geology" since then, so not all of Scotland looks like all of Norway.
Another curious point to note is that the extreme northwest of Scotland has Cambrian fossils which are nothing like any you will see in the rest of Europe. They are in fact akin to North American fossils. They were an accidental 'left behind' when the Atlantic started spreading. That is when Scotland and Newfoundland were close neighbours.
Also, as TonyC points out, both Norway and Scotland (and in fact all of NW Europe, have also been sculpted by the very recent (in geological terms) glaciation.