Geno is actually a supernatural being sent to repair the Star Road that Smithy broke. Mallow is not really a frog (which you can tell by looking at him), but the prince of Nimbus Land, a floating kingdom of cloud-people. Bowser the Koopa King, Mario's old arch-nemesis, and Princess Toadstool both end up joining the group to stop Smithy from robbing the world of the Star Road and, with it, all wishes made on stars (sounds sappy, I know, but Smithy is kind of a cool villain).
Among the subplots engaged in by the team is the Booster story, in which Booster, a raggedy, bearded, viking-looking kind of guy who's a few monkeys short of a barrel, kidnaps the Princess and tries to marry her in the lavish town of Marrymore. After a chase and a fight with a monster cake in the Marrymore cathedral, the gang succeeds in stopping him and his band of Snifit lackeys, along with the clownish Knife Guy and Grate Guy, the latter of whom opens a casino later in the game.
Also, as mentioned above, Mallow's revelation about his true heritage comes at a price, for he has to win back his claim to the Nimbus Land throne after a prissy gold-digger named Valentina uses a Mallow imposter to take the kingodm for herself. As it happens, Valentina is driven for Nimbus Land, and she and her dim-witted assistant Dodo end up landing on Booster's tower. During the end credits to the game, we see Valentina and Booster together at the Marrymore cathedral.
I don't need to tell you that Smithy is beaten and his gang is driven back to the world from which they came, and everybody (else) lives happily ever after.