There are a few definitions for deus ex machina, but the one I’m using here (courtesy of is “An unexpected, artificial, or improbable character, device, or event introduced suddenly in a work of fiction or drama to resolve a situation or untangle a plot.” It is, by definition, stupid and evil and not something you want to have around. Even the mildest definition, “unexpected,” points to a failure in the story, since something introduced well enough can be traced back by the reader and admitted as part of the story without straining suspension of disbelief. So this is a list of ways to avoid reaching for one of those gods by machine at a critical juncture in the plot.

1) Don’t bring in an outside force or person or god to settle the conflict.

This can seem obvious, since it’s the very definition of deus ex machina, but it’s something that fantasy tends to suffer from. The protagonist gets himself or herself into a corner, and suddenly there’s the wise old wizard with a solution, or a goddess who chooses the heroine her champion, or some ancient, evil dragon awakened by the bad guy who picks that moment to turn on him. Even a little of this is far too much. It not only shatters the story and reminds the reader that she’s holding nothing but paper in her hands; it also makes your protagonist seem nothing more than lucky. Usually, there’s no mention of the protagonist being so worthy that the goddess chose that moment to show up, or the dragon rebelling after a long period of mistreatment. It just happens, and the hero or heroine escapes (with the treasure and the girl or guy, of course), full of undeserved good fortune.
If you know that a powerful force is going to show up and save the day, it has to be mentioned at numerous points in the story, long before it does save the day. The goddess should put the protagonist through a series of tests, or tell her that after she fulfills some task, then she’ll get an infusion of godly strength. Even then, the motivation should be reasonable, or the goddess will resemble a petty child who insists on almost breaking her toys before she deigns to step in and do what she could have done since the beginning of the story. I have heard objections that if the goddess steps in too early, there will be no story. Well, exactly. A tale that could be solved by something simple happening in the first fifty pages is not a tale that deserves to be told. The author has to come up with logical ways of stretching out the tension, and making the goddess change her mind for no reason just at the most convenient point for the heroine is not one of them.
Also, if a mortal king or lord suddenly decides to join the conflict against the bad guy and provides the necessary manpower to topple him, there have to be reasons for that, too, particularly if he was moodily refusing to come out of his castle until then. It’s always best to show the change of heart, either before or after the fact. (This is another reason why telling a fantasy story through multiple narrators if possible is a good idea). A calculated stroke falling at just the moment when the bad guy believes he’s won is much better, more awesome, and more impressive than an evil lord deciding to turn good because “it’s the right thing to do.”
If you come up with the idea for the outside force on the spur of the moment, be prepared to do a lot of rewriting and retrofitting of the story into its correct path. Or just drop it, let your protagonist suffer through it, and have the climax play out more darkly than you had originally intended.

2) If the backstory plays a large part in the present story’s resolution, it needs to be introduced as soon as possible.

Spoilers for Anne Bishop’s Black Jewels trilogy follow.
At the end of the trilogy, Jaenelle, who’s practically a goddess all by herself, comes up with a way to get rid of evil forever. However, that way depends on a story that we haven’t been told yet—a story that was detailed only in The Invisible Ring, a book that Bishop published a year later than the trilogy. In the trilogy itself, it’s related very hastily by another character, who himself heard it secondhand. Jaenelle decides it’s the only way that will work, adopts it, and, surprise no surprise, it works.
This should not be allowed to happen in a well-constructed fantasy. If you know that your character has the necessary skills to survive the ending, but you haven’t showed him developing those skills in the present story, then mention them early, mention them often, and, ideally, show them in smaller operation somewhere else. It’s much easier to believe that a character could do an exaggerated version of something he was doing all along than believing that, “Oh, yeah, in an adventure I never said anything about until just now, he acquired the Tongue of Tupin and the knowledge of the Riddle of Gavlere!” You may know your own canon backwards and forwards, but you can’t require that your audience know those kinds of things about unpublished books or adventures that exist only in character profiles. If you tack them on at the end, they’ll feel you’re pulling things out of the air, and rightly so.

3) Don’t ignore the obvious.

There are several times I’ve read a fantasy book and wondered why the heroine or hero didn’t simply walk right out of the cell, when earlier they’d been shown having the ability to pass through walls; or fly to the top of a wall, since earlier they could transform into a raven; or sneak across a room quietly, since they’d had training to do so. The authors too often ignored solutions they’d built into the story. Whether it was through wanting a big, dramatic climax, something more showy than just a raven flying to the top of a wall with a grappling hook, or whether they’d actually forgotten, I’ll never know. But any author worth her salt should be sharper-eyed.
If you’re the kind of writer who plans out her story’s resolution in advance (as most of the writers I meet seem to be), then study every element, and ask yourself whether it couldn’t be subverted by something else in the story. If the answer is yes, either go with the simpler solution, which is less likely to feel like a deus ex machina, or come up with some way to disable that ability, person, or trick. Be careful, though. Too many disabilities, and your ending can feel like a house of cards, once again leading to the deus ex machinasyndrome.
Another, perhaps simpler way to do it is just not to pile so many special abilities on your characters. If you don’t forget that they can turn into ravens, and have to work with that one fact all through the story, you’re less likely to toss it out the window when the big finale comes.

4) Establish some rules of magic that you will never break, not even for your characters.

I imagine that love of their created characters, as well as love of writing about unique people, lies behind many fantasy writers’ tendencies to make their people the Most Special Magic-Users Ever. So the character can do magic that no one else of his gender can, or magic that no one else of his race can, or magic that no one’s been able to do in a hundred years, or magic that was last seen in his great-grandfather and that he shouldn’t have inherited, and so on. The author brings in fate or destiny to explain it away, and then often bends the rules further, so that something impossible even for that character does occur at the end of the book. If magic isn’t supposed to bring back the dead, it will reverse itself for the hero’s dead best friend or beloved. If the heroine absolutely cannot pick up a mountain, then rest assured she’ll find the strength to do it when smashing the bad guy.
Stop that.
At some point, the rules have to stand firm, or you begin to have an “anything-goes” fantasy world, where the main characters could probably just wish the villain away if they tried hard enough. And the explanations for why this one particular impossible thing is happening for this one particular person get to sound flimsier and flimsier.
You should empathize with your characters, all your characters. But don’t sympathize with them. Don’t start feeling as if their goals are your goals and you have to make sure the characters achieve them or you’ll feel terrible, because if you get to that point, you’re going to introduce a deus ex machina without blinking twice.
Have some rules of magic that are final. No exceptions, no taksies-backsies. The characters will be forced to fall back on what they have, instead of what they want, and they might surprise you. And it’s possible to do wonders with a handful of nothing. People do it all the time in our world, without magic, and in plenty of good fantasies with nothing more than intelligence and courage.

5) Remember that not all surprises are good ones.

A good surprise is pretty much a must of a deus ex machina. Someone the character barely remembers comes up and saves his life. Aid he never expected from a god descends from heaven. Something he never knew his powers could do happens. A lot of fantasy authors try to explain this as a result of chance or good storytelling, though unless it has a good basis to rise from, something the reader could have guessed even though she didn’t, it still looks like the author meddling where she has no business to meddle.
But why does a surprise need to resolve a plot? Why not have a nasty one that comes along and complicates it further, perhaps into something that the characters or you, the author—if you’re stuck behind writer’s block—can solve, where before they were trotting complacently along?
I always wanted to see a fantasy where the hero looks to someone to save him, such as the faithful sidekick who’s hinted that she’ll sacrifice her life so that he can be happy with his true love, and hears that person say, “No.” In some fantasies, it would work a hell of a lot better with the established storyline and characters than the unquestioning act of self-sacrifice. It would also force the hero to fall back on his own resources, and maybe save his own ass. And it would give the sidekick the ability to shine, if only for a moment, and step beyond the role of corny plot device.
This would also require build-up, of course. But nasty surprises don’t require as much as good ones do, I think. Readers are often more willing to accept something that complicates the plot and forces the hero to think fast than they are something that steps up and wraps everything in a nice package with a bow on the top. They also are more likely to work with the prevailing temper of some stories. If the hero’s been slagging all over the sidekick during the story, I sigh when she steps up and sacrifices her life. She was only there for one reason, then, and the author’s just proved it. Something that displays a spark of independence and spirit would make me cheer for her, even though I know the hero’s still probably going to win. It also makes the victory that much more interesting.
Don’t just think about the wonderful secrets that are going to fall from the sky. Think about the nasty secrets hiding in the closets.
If the majority of authors do outline, as I’ve been assured they do, it puzzles me why so many fantasy stories feel forced and contrived in their endings. Maybe they just need to do more rewriting.