Just as a point of fact, many Native American tribes/nations were not nomadic. The nomadic nations of the great plains represented only a fraction of the Native American peoples. (I use past tense here only in reference to the fact that none of the major tribal groups are currently living a nomadic lifestyle.)

Not only were not all American Indians not nomadic, but not all nomadic societies had the same sort of social organization- in fact, they range from aggressively egalitarian to extremely hierarchical slave societies and had accordingly different ways of dealing with rule breakers. The concept of a "criminal" wouldn't make sense in a lot of them because they didn't have the kind of legal system that would define misbehavers that way.

For example, most San peoples (descendants of the indigenous foragers of Southern Africa) were nomadic and many lacked any kind of formal leadership or legal system. A person in many San societies could do whatever they wanted without legal consequences- but not without social consequences.

Norms such as food sharing, humility in hunting success, and egalitarianism were enforced through relentless teasing and arguing. More serious disagreements and arguments could get heated and lead to deadly fights and potentially a feud between friends and family of the fighters (research on homicide among the Ju/'hoansi in the early 20th century found that while they weren't in some Pinkerian state of constant warfare, the homicide rate was still higher than for most cities in 20th century America). To diffuse tension the small bands people lived in could split along faultlines to keep enemies apart and not at each other's throats with spears and poison arrows.

What about someone who simply didn't care about getting along with people? Richard B. Lee (who compiled the Ju/'hoansi homicide data in the mid-20th century through interviews) found a case of a man who was probably psychopathic and had killed three people in fights over petty things. The regular Ju/'hoan social controls wouldn't work on him so several men in the area got together, went to his camp, and executed him.

In Romani (gypsy) groups, there would be a trial, called a kris, in which elders would hear all sides of the story and decide on a punishment, the most severe being shunned by all Romani people. This is terrible, as Rom are taught that non-Roma (gadje) are dirty and spiritually polluting. The famous poet Papusza was shunned and " She spent great periods of her life in silence and died disgraced." Association with gadje, by choice or punishment means you are declared marime, or spiritually dirty. http://www.vidaweb.org/twenty-gypsy-women-you-should-be-reading/

You might get a better answer by being more specific with your question. There have been quite a lot of nomadic societies in history with wildly different cultures and practices.

Counter question: who are the "crimes" you can commit in a nomadic hunter-gatherer band of ~30-60 people who only have communal property?

In the Forest People Colin Turnbull described the aftermath of breaking the incest taboo amongst the Ba-Mbuti in Congo:

We had all eaten in the evening and were sitting around our fires. It was with Kenge and a group of the bachelors, talking about something quite trivial, when all of a sudden there was a tremendous wailing and crying from Cephu's camp. A few seconds later there was shouting from the path connecting the two camps and young Kelemoke came rushing through our camp, hotly pursued by other youths who were armed with spears and knives. Everyone ran into the huts and closed the little doorways. The bachelors, however, instead of going in with their families, ran to the nearest trees and climbed up into the lower branches. I followed Kenge up one of the smaller trees and sat among the ants, whose persistent biting I hardly noticed. What was going on below took all my attention,

Kelemoke tried to take refuge in a hut, but he was turned away with angry remarks, and a burning log was thrown after him. Masisi yelled at him to run to the forest. His pursuers were nearly on top of him when they all disappeared at the far end of the camp.

At this point three girls came running out of Cephu's camp, right into the middle of our clearing. They also carried knives — the little paring knives they used for cutting vines and for peeling and shred- ding roots. They were not only shouting curses against Kelemoke and his immediate family, but they were weeping, with tears streaming down their faces. When they did not find Kelemoke, one of them threw her knife into the ground and started beating herself with her fists, shouting over and over again, "He has killed me, he has killed me!" After a pause for breath she added, "I shall never be able to live again!" Kenge made a caustic comment on the logic of the state- ment, from the safety of his branch, and immediately the girls turned

their attention to our tree and began to threaten us. They called us all manner of names, and then they fell on the ground and rolled over and over, beating themselves, tearing their hair, and wailing loudly.

Just then there came more shouts from two directions. One set was from the youths who had evidently found Kelemoke hiding just outside the camp. At this the girls leaped up and, brandishing their knives, set off to join the pursuit. The other shouts, for the first time from adult men and women, came from the camp of Cephu. I could not make out what they were about, but I could see the glow of flames.

I asked Kenge what had happened. He looked very grave now and said that it was the greatest shame that could befall a Pygmy— Kelemoke had committed incest. In some African tribes it is actually preferred that cousins should marry each other, but among the Ba- Mbuti this was considered almost as incestuous as sleeping with a brother or sister. I asked Kenge if they would kill Kelemoke if they found him, but Kenge said they would not find him.

"He has been driven to the forest," he said, "and he will have to live there alone. Nobody will accept him into their group after what he has done. And he will die, because one cannot live alone in the forest. The forest will kill him. And if it does not kill him he will die of leprosy." Then, in typical Pygmy fashion, he burst into smothered laughter, clapped his hands and said, "He has been doing it for months; he must have been very stupid to let himself be caught. No wonder they chased him into the forest." To Kenge, evidently, the greater crime was Kelemoke's stupidity in being found out.

All the doors to the huts still remained tight shut. Njobo and Moke had both been called on by the youths to show themselves and settle the matter, but they had both refused to leave their huts, leav- ing Kelemoke to his fate. Now there was an even greater uproar over in Cephu's camp, and Kenge and I decided to climb down from the tree and see what was going on.

One of the huts was in flames, and people were standing all around, either crying or shouting. There was a lot of struggling go ing on among a small group of men, and women were brandishing fists in each other's faces. We decided to go back to the main camp, which by then was filled with clusters of men and women standing about discussing the affair. Not long afterward a contingent from Cephu's group came over. They swore at the children, who, delighted by the whole thing, were imitating the epic flight and pursuit of Kelemoke. The adults, in no joking frame of mind, sat down to have a discussion. But the talking did not center around Kelemoke's act so much as around the burning of the hut. Almost everyone seemed to dismiss the act of incest. One of Kelemoke's uncles, Masalito, with whom he had been staying since his father died, had great tears rolling down his cheeks. He said, "Kelemoke only did what any youth would do, and he has been caught and driven to the forest. The forest will kill him. That is finished. But my own brother has burned down my hut and I have nowhere to sleep. I shall be cold. And what if it rains? I shall die of cold and rain at the hands of my brother."

The brother, Aberi, instead of taking up the point that Kelemoke had dishonored his daughter, made a feeble protestation that he had been insulted. Kelemoke should have taken more care. And Masalito should have taught him better. This started the argument off on different lines, and both families quarreled bitterly, accusing each other for more than an hour. Then the elders began to yawn and say they were tired; they wanted to go to sleep; we would settle it the next day.

For a long time that night the camp was alive with whispered remarks, and not a few rude jokes were thrown about from one hut to another. The next day I went over to Cephu's camp and found the girl's mother busy helping to rebuild Masalito's hut; the two men were sitting down and talking as though nothing much had happened. All the youths told me not to worry about Kelemoke, that they were secretly bringing him food in the forest, he was not far away.

Three days later, when the hunt returned in the late afternoon, Kelemoke came wandering idly into the camp behind them, as though he too had been hunting. He looked around cautiously, but nobody said a word or even looked at him. If they ignored him, at least they did not curse him. He came over to the bachelor's fire and sat down. For several minutes the conversation continued as though he were not there. I saw his face twitching, but he was too proud to speak first. Then a small child was sent over by her mother with a bowl of food, which she put in Kelemoke's hands and gave him a shy, friendly smile.

Kelemoke never flirted with his cousin again, and now, five years later, he is happily married and has two fine children. He does not have leprosy, and he is one of the best liked and most respected of the hunters.