Warning: Wikipedia contains spoilers.
Cap'n Bill, a sailor with a wooden peg-leg, and his friend, a little girl named Trot, set out from California on a calm day. The calm day suddenly turns dark and stormy and Cap'n Bill and Trot and washed overboard and are carried by mermaids (referred to but not seen) to a cave where they meet an ostrich-like flying bird called an Ork. Flying on the Ork's back, the Ork, Cap'n Bill and Trot strain to arrive at an island where a grim man calling himself Pessim the Observer points out that the Ork shouldn't have eaten the light lavender berries growing on the island. The light lavender berries cause a person to shrink, and the dark purple berries cause a person to grow. Once the Ork resumes normal size, Cap'n Bill and Trot leave the island to escape the Observer's negative attitude—which drove the people in his homeland to exile him here in the first place. To reduce the load on the Ork, Cap'n Bill and Trot each eat a light lavender berry so they're small enough to carry in a handkerchief.
Flying away from the island, Cap'n Bill, Trot, and the Ork alight in the land of Mo, one of Baum's non-Oz creations. They meet the Bumpy Man, who specializes in serving sugar and molasses and has some of their appearance too. After dining on Mo rain (lemonade) and Mo snow (popcorn), they run into Button Bright, the sailor boy from The Road to Oz who's gotten lost again. Cap'n Bill calls down some of the native birds (who, like all birds in fairy countries, can talk back) and offers them the dark purple berries to make them grow large enough to carry himself, Trot, and Button-Bright (for the Ork can fly) to the land of Oz across the Deadly Desert to the north of them. When they make it across the desert, Button-Bright, Cap'n Bill, and Trot are set down in a field and the Ork leaves them to find his own country, which he got lost from on a routine flight.
The place Button-Bright, Cap'n Bill, and Trot have arrived in, Jinxland, has had a turbulent recent history. The rightful king of Jinxland, King Kynd, was killed by his prime minister Phearse, who was in turn killed by his prime minister Krewl. Now King Krewl rules over the land and seeks to marry King Kynd's daughter, Princess Gloria, to legitimize his claim to the throne. But she wants nothing to do with him or another suitor, Googly-Goo; she is in love with Pon, the current gardener who is the son of the first usurper Phearse. King Krewl and Googly-Goo decide that if neither of them can have Gloria, no one can, and hire a witch named Blinkie to freeze her heart so she can love no one. Cap'n Bill happens on this plot, and to keep him from interfering, Blinkie turns him into a grasshopper.
The Scarecrow is at Glinda's palace in the Quadling Country and learns about these events from reading Glinda's Great Book of Records, a magical volume which transcribes every event in the world at the instant it happens. The Scarecrow wants to help Cap'n Bill, Button-Bright, and Trot, and Glinda sends him to Jinxland with some of her magic to aid him. The Scarecrow uses a magic thread to cross the gorge separating Jinxland from the rest of the Quadling Country, and before he meets Cap'n Bill and Trot, he encounters the Ork, who has found his homeland. The Scarecrow attempts to depose Krewl and is captured, with Googly-Goo suggesting the Scarecrow be burned, but then the Ork arrives with fifty others who attack the Jinxlanders and turn the tables on Krewl. The victorious party then arrive at Blinkie's and make her undo her magic on Cap'n Bill and Princess Gloria by using a magic powder to shrink her in size. When she has undone her evil spells, the Scarecrow stops Blinkie's shrinking, but she remains at a small size and loses all her magic powers.
Gloria takes the throne of Jinxland and elevates Pon to be her royal consort, and the Scarecrow, Button-Bright, Cap'n Bill, Trot, and the Orks return to the Emerald City for a celebration.