Warning: Wikipedia contains spoilers.
Queen Ann Soforth of Oogaboo, a small monarchy separated from the rest of Oz's Winkie Country, sets out to raise an army to conquer Oz. Seventeen men eventually make up the Army of Oogaboo (out of eighteen men, twenty-seven women, and forty-four children) and they march out of their valley. Glinda magically rearranges the path through the mountains and Queen Ann and her army march out of Oz entirely into a low-lying, befogged country.
Betsy Bobbin, a girl who's a year older than Dorothy Gale, and her loyal mule Hank are washed ashore during a storm. They arrive at a large greenhouse that is the domain of the Rose Kingdom, where they're told by the roses that no strangers are allowed. Just as the Royal Gardener (apparently the only human allowed in this flowery kingdom) is about to pass sentence on Betsy and Hank, the Shaggy Man falls through the greenhouse's roof and, with the Love Magnet he carries, charms the Gardener into sparing all of their lives. But the flowers, not having hearts, are unaffected by the Magnet and force the travellers to leave, taking with them the newly plucked Rose Princess Ozga, a cousin of Ozma, the ruler of Oz.
The Shaggy Man relates how Ozma sent him here by means of the Magic Belt because he wanted to find his brother, who went digging underground in Oklahoma and disappeared. He surmised that the Nome King, ruler of the underground Nome Kingdom, captured him and now the Shaggy Man seeks to free him. They meet up with Polychrome the Rainbow's Daughter who danced off her rainbow again and come upon a water-filled well in which they see a large object bobbing. With great effort, they retrieve the object and find that it's Tik-Tok, a copper mechanical man (who today would be called a robot, a term that didn't exist when this was written) sent by Ozma due to his familiarity with the Nome King, to help the Shaggy Man. But the Nome King found him first and threw him down the well. Once Tik-Tok is wound up, he accompanies Betsy, Hank, the Shaggy Man, Ozga, and Polychrome to their chance encounter with Queen Ann and her army. In a rage, Queen Ann orders them to be seized and bound, but Private Files -- the only private in this army of generals, colonels, and majors -- refuses to bind innocent girls. He resigns his commission on the spot, and only when Queen Ann is told about the Shaggy Man's quest and the riches to be found in the Nome King's underground kingdom does she calm down and accept the services of Tik-Tok as her new private.
The Nome King (who despite his drinking the Water of Oblivion in The Emerald City of Oz did not forget his wickedness) is aghast at this group coming toward his underground kingdom and planning to plunder it (in the case of the Army of Oogaboo) and retrieve his captive (in the case of the Shaggy Man). Since he can't kill them (in a fairy land like Oz or any of its neighbors, no one can die), the Nome King seeks to discourage them by first taking them through the Rubber Country and then disposing of them by dropping them through the Hollow Tube, a conduit leading to the other side of the world. With his magic, the Nome King makes the opening of the Tube invisible so they all fall into it.
On the other side of the world, the party enters the kingdom of the Great Jinjin, who vows to punish the Nome King for using the Tube by taking his kingdom from him. He sends Tik-Tok and the others back with his Instrument of Vengeance, a lackadaisical dragon named Quox. Quox and his riders bound from the other end of the Tube into an army of Nomes and narrowly evade them. Queen Ann and the Army of Oogaboo fall into the Slimy Cave when they enter the Nome Kingdom while Betsy, Files, Hank, Polychrome, the Shaggy Man, and Tik-Tok find themselves captured by the Nome King himself. Queen Ann and her army escape the cave while the Nome King amuses himself by transforming his captives into various objects before Quox arrives, bursting through the main cavern. Once the Nome King sees the ribbon around Quox's neck, he forgets all the magic he ever knew. The Nome King is driven out of his kingdom when Quox releases six eggs from the padlock around his neck. The eggs, which are poisonous to Nomes, follow the Nome King to the earth's surface and exile him there.
The new Nome King, the former chief steward Kaliko, vows to help the Shaggy Man find his brother, who he knows is in the Metal Forest -- but only the exiled former king knows where that is. The Nomes report to King Kaliko that they found the secret passage he used to enter the forest, and Betsy and her companions follow him. The Great Jinjin sentenced the former Nome King to walk the earth forever, but he let him have as much treasure as he could carry in his pockets, which are overflowing by the time they catch up to him.
The Shaggy Man meets his brother in the center of the Metal Forest, but he was cursed with a charm of ugliness by the former Nome King, who doesn't remember how to undo it. Straining his memory, he recalls that a kiss will break a charm of ugliness. First a mortal maid, Betsy, tries to undo the spell; then a mortal maid who was once a fairy, Ozga, and finally Polychrome, a fairy whose kiss restores the Shaggy Man's brother to his former self.
There is a banquet of rejoicing in the Nome Kingdom, and the former Nome King earnestly pleads to be let back into the underground lair ("No Nome can really be happy except underground."), which Kaliko allows on condition that he behave himself. Once on the surface again, Polychrome ascends her rainbow and Ozma uses the Magic Belt to bring Tik-Tok back to Oz and send Queen Ann, the Army of Oogaboo, Files, and Ozga back to Oogaboo. The Shaggy Man only agrees to return when his brother, Betsy, and Hank are allowed to enter Oz too -- violating a precedent against admitting mortals helter-skelter into the land of Oz.
Upon being welcomed in Oz, Hank, the Cowardly Lion, the Hungry Tiger, and the Saw-Horse debate who is the best mistress -- Betsy (for Hank), Dorothy (for the Lion and the Tiger), or Ozma (for the Saw-Horse). The three girls are listening and laugh at a silly quarrel, which the animals realize is silly too. And Dorothy finally gets to hear her dog Toto speak -- for all animals can in the land of Oz.