I've heard that the prefix
Mc- or
Mac- in a person's name can be replaced by
son of-. For example:
McArthur can be understood as
son of arthur. I think the intention was to say what
clan you belonged to. So if you met
Pidi from the clan of the
Cloud, you could call him
Pidi McCloud. The later use in family names is pretty natural from there.
ooh! just found a node mentioning that: Irish Gaelic family names
Update: gleeme says: a similiar prefix Fitz- (e.g. as in "Fitzpatrick") means bastard son of while Mc- means legitimate son of.