Warning: Wikipedia contains spoilers.
Uncle Henry has been ordered by his doctor to take a vacation from his Kansas farm to Australia. He and his niece Dorothy Gale are aboard a steamship travelling there when they are caught in a fierce storm and separated. Dorothy is blown overboard along with a yellow hen from her uncle's farm that was on the ship.
Dorothy and Billina -- the name, derived from "Bill", given the yellow hen soon after it was discovered that she wasn't a rooster -- wash ashore and pick something to eat from a lunch-pail tree. Dorothy guesses that they're in a "fairy country" because lunch pails don't normally grow on trees and animals like Billina don't talk, but it's a different one from Oz because that country has no seashore. They come across a message inscribed in the sand, "BEWARE THE WHEELERS", and soon meet these gaudily-dressed, loudly-yelling creatures who roll on wheels in place of walk on hands and feet. Dorothy and Billina climb a rocky mountain to escape the Wheelers and find a door carved into its side. Finding the key by the door, they open it and find Tik-Tok, a round mechanical man who they activate with the key.
Tik-Tok tells Dorothy and Billina about the land of Ev where they are now and the loss of its royal family to the magic of the Nome King. He takes them to safety from the Wheelers to the royal residence, where the head-exchanging Princess Langwidere, the sister of the deceased king of Ev, locks Dorothy and Billina in a high tower. Tik-Tok stops once in mid-motion, and he won't be able to move again until he is wound up with the key.
Ozma and her companions (many of whom appeared in the two previous Oz books) cross the Deadly Desert with the aid of a magic carpet provided by Glinda to free the royal family of Ev, and Ozma has Dorothy released from Langwidere's custody. Cheerful reunions are had by the Scarecrow, the Tin Woodman, and the Cowardly Lion, and new introductions are made to Ozma and the Hungry Tiger, a massive tiger hamstrung by his conscience.
The expedition journeys to the underground kingdom of the Nomes, where the Nome King reveals that he's turned the royal family into ornaments around his palace. The Oz people can guess which ornaments they are (he doesn't reveal that they are royal purple ones), but if they fail, they will also become ornaments. Ozma, the twenty-seven soldiers of the Royal Army of Oz, the Tin Woodman, the Scarecrow, and Tik-Tok all suffer this fate (Dorothy only escapes it by touching a purple ornament in one of her guesses). When the guests from Oz retire one night, Billina learns which of the Nome King's ornaments were once people and also about the Magic Belt which he wears.
Billina was originally not going to be allowed to guess, but she so infuriates the Nome King by laying an egg (poisonous to any Nome) under his throne that he lets her guess. And all of hers turn out to be right! The Nome King commands his army to recapture all of them by force, but Dorothy takes the Magic Belt, the Army's sole private takes the offensive, and Billina's eggs are left in the Nomes' paths so they don't dare follow.
After returning the royal family of Ev (the queen mother, five boys, and five girls) to their rightful place, Ozma, Dorothy, and the others return to Oz where a great victory celebration is held in the Emerald City. Dorothy is officially made a Princess of Oz, Billina elects to remain in Oz, and Ozma uses the Magic Belt to send Dorothy to Australia to be reunited with Uncle Henry.