The origin (for our purposes) seems to go back to Leviticus 6:2 where "the giving of the hand" was an idiom for "fellowship" of some kind. The full import of what that might express specifically may be lost to history, however in the context of 6:2 it seems to have expressed something that could be betrayed.
Adam Clarke writes:
Giving the right hand to another was the mark of confidence,
friendship, and fellowship. See Lev_6:2 : If a soul - lie unto his
neighbor in that which was delivered him to keep, or in fellowship,
בתשומת יד bithsumeth yad, “in giving the hand.”
KJV Lev 6:2 If a soul sin, and commit a trespass against the LORD,
and lie unto his neighbour in that which was delivered him to keep,
or in fellowship , or in a thing taken away by violence, or hath deceived his neighbour;
Update
So what the right hand seems to express is trust as if to say that "Okay, we have confidence Paul, that you are, like us, committed to God and we believe that we can count on you to do the right thing and not betray our trust".
In modern culture we also perform the ritual of shaking hands but generally without understanding it to be a commitment. However, often it is viewed as a commitment even today and an agreement is often signaled by the ritual and we agree to "shake on it".
Conversely, if someone breaches trust one is generally loathe to extend our hand for a shake.
Update 2
It occurs to me that the gesture can be contrasted with this, largely opposite gesture:
Luke 9:5 And whosoever will not receive you, when ye go out of that
city, shake off the very dust from your feet for a testimony against
them.
Update 3
I found this interesting. Strong's G782 is translated in the KJV variously as in the following manner: salute (42x), greet (15x), embrace (2x), take leave (1x). It is also the word used above, in Luke 9:5: "whosoever will not receive you".
The etymology is what is so interesting:
ἀσπάζομαι aspázomai, as-pad'-zom-ahee; from G1 (as a particle of union) and a presumed form of G4685; to enfold in the arms, i.e. (by implication) to salute, (figuratively) to welcome:—embrace, greet, salute, take leave.
So the etymology paints a picture of someone "not folding their arms". That's kinda Zen! But the idea seems to be that if you have, for example, Christ in common you "open your arms" and if you have nothing in common, IE: do not have Christ in common with someone you fold your arms.
However, in Luke 9:5 the idea is "welcome" as in "welcome as a guest in their home" with the implication being that if they welcome Christ with open arms they receive his emissaries in the same way.