When does a partially random event go from reasonably possible to contrived "deus ex machina"?

The infamous "with one bound, our hero was free" is deus ex machina; "our hero turned the corner and smashed into (anything)" might be random but it's also reasonable.

Can you show how it could matter that the event was "random" - wholly or partially?

Several answers have the same message: its the resolution of conflict that makes deus ex machina a problem. I would recommend using a phrasing from Brandon Sanderson: his First Law of Magic

Sanderson’s First Law of Magics: An author’s ability to solve conflict with magic is DIRECTLY PROPORTIONAL to how well the reader understands said magic.

The message is the same, but I find that, as a writing tool, calling it "magic" is a really effective way to get a feeling for how bad it is. Magic admits these coincidences for what they really are, no punches pulled. Throw that word around with regard to your own work, and you quickly find out what you are comfortable with.

If you aren't comfortable arguing why your particular plot device should not be treated as if it were magic, then you should apply Sanderson's Law. Look at how much conflict you resolved, and how well the reader understands the nature of the device.

What if the MC had used divination to put himself on the path of this native? Would it feel contrived? This might depend on a host of show-don't-tell sort of things. If you show that he's actively trying to capitalize on small things, no matter how small, getting lucky may be less luck and more a subtle skill. On the other hand, how much conflict is actually being resolved? If you're actually creating conflict in the process, you can get away with a whole lot of this kind of magic! Maybe going after that one particular camp to reclaim two people is a bit of a doozie!

Author Shirley Hazzard:

I've thought that there may be more collisions ... in life than in books. Maybe the element of coincidence is played down in literature because it seems like cheating or can't be made believable. Whereas life itself doesn't have to be fair, or convincing.

From The Transit of Venus, Viking Press, New York, 1980, p. 62.

All literature relies on coincidence. That's because a narrative isn't a duplicate of life, it's a condensation of it, where things are brought into close proximity for maximum effect. So the audience is prepared to accept a certain amount of coincidence.

The general rule of thumb is this. Coincidence feels like a cheat when it makes things easier for the characters, illegitimately, which is to say, without them putting the work in. The detective happens to find the stolen jewel in the first pawn shop he finds. Everyone groans. But when it makes things harder for the characters, it's much more palatable. Why, of all the gin joints in all the towns in all the world, does Ilsa walk into Rick's? Who cares, it's the challenging event that sets the story in motion. The underlying reason is that we read to learn. We can learn a lot from seeing a character deal with an unlucky break. But we can't learn anything from watching someone who's undeservedly lucky all the time.

If coincidence is doing too much water-carrying for the writer, that can get annoying as well. If the writer consistently relies on improbable coincidences to put the characters in interesting situations, that begins to feel real fake, real fast. In the last Harry Potter, is it a string of coincidences that the villain is reliably able to find the hero? No, it turns out there's a hidden mechanism at work. Again, it comes down to being able to relate it to our own lives and challenges. A long string of meaningless unlucky breaks doesn't feel any more real than a long string of lucky ones.

When we talk about what is plausible or implausible in a story, we tend to approach causality front-to-back:

What are the chances you'd survive falling out of an airplane in flight?

Obviously, they are not good at all. If you're faced with the choice to jump from an airplane in flight, you expect it to be suicide - because the chances of survival are that low. On the other hand...

What are the chances that someone telling you about the time he jumped from an airplane survived?

Setting aside cases where he is still falling while talking to you, or stories about an afterlife (or dishonesty about having jumped on the part of the teller), the chances of surviving the fall go from effectively nil to 100%.

What does this have to do with the implausibility of events in a story? Simple; if interesting and unusual things didn't happen in your story, you wouldn't be telling it. That is, looking at probability from back-to-front, you're not (closely) telling the story of the Native Americans who had trouble with the gold miners and DIDN'T meet someone else who was having problems with them. You're not telling the story of white frontiersmen who were killed by Native Americans, and never inspired mercy or realized they had a common cause.

As long as your story takes place in a universe where not every convenient coincidence that could happen does happen, most readers will have some patience that a few coincidences come up in your story. Something interesting must have happened - because you're telling it.

Obviously you're making it all up, but "These are unusual things that don't happen all the time, but are worth telling about," is a principle on which most stories are modeled.

Does not look extremely unlikely. Of course it would depend on how large the area the tribe uses to move in is. They were nomadic but inside well defined and known areas.

Eventually he makes it out of the forest and nears Texas again, returning to the Great Plains. He does this because he figures it will be easier to spot people on the Plains than in the desolate woods. And spot people he does.

You could make the encounter even more likely if the MC were to follow a likely path, like a water way. Would be most common for people of the age to move and camp along rivers. So meeting is almost inevitable if the two different parties are moving in opposite directions.

I'd say this isn't a deus ex machina - those usually occur suddenly, resolve the story's conflict/dramatic tension, and in many cases occur from outside the narrative context.

Here you've essentially got a co-incidence (which aren't actually as unlikely as you'd might think) - two aggrieved parties with a common foe encounter each other and team up. This is then driving the plot forward, setting up the conflict (both literal and figurative) in the next act.

Yes it's fortunate for the MC that he encountered someone inclined to help him and it's fortunate for the native(s) that they encountered someone with information valuable to them (the knowledge of the daughter) and yes it's probably more likely in the real world for them not to have run into each other but this isn't the real world, it's fiction and suspension of disbelief will get you along just fine.

This doesn't resolve all the MC's and the Native's problems - they still have a gang of evil gold miners to face off and a damsel to rescue. Adventure, peril and general hi-jinks ensue.