In Chapter 1, a thumb is cut from a VC corpse, after which character Mitchell Sanders says, "...there's a definite moral here" and, later, "...it's like with that old TV show - Paladin. Have Gun, will travel." What does the reference to Have Gun, will travel (which I remember) have to do with the"definite moral here."

The quotation about the severed thumb joins the experiences of the four men directly involved: The soldier whose thumb it was; Sanders, who cut it off and commented that there was a moral; Bowker, to whom he gave it and who carries it; and Dobbins, who did not see that there was a moral.
The author notes superstition as a possible reason, mentioning a pebble and a rabbit's foot. He describes Bowker as "gentle." Why Sanders would give him the thumb and why he would accept it are left unstated. Sanders, apparently, is not gentle--he kicks the corpse in the head.
It is left to the reader to decide if Dobbins is right about the moral, or if Sanders was right to remove it in the first place. It seems that O'Brien is suggesting that the reader suspend judgment, through the words, "There it is man."
"Have gun, will travel" seems to be an ironic interpretation of what these men are doing. They carry their guns and progress through the countryside, either surviving and dying. The person who lives can gain the power to mutilate the dead. The war might have no more meaning than that for them. (The association with the TV show would not have been remote, as the war was in the 1960s.)