Here's how I think the story will play out:
Mario and Kirby are having a friendly match in the arena when the Halberd, being driven by the Ancient Minister, appears to swallow the arena in subspace with a Subspace Bomb. He sees that Mario and Kirby who are potential threats are already there, and sends down an army of Prymids to attack them. Seeing this, Peach and Zelda come down to help fight. Then the first level begins, where I believe the fight will be either Mario vs the Prymids, or Mario, Kirby, Peach, and Zelda vs the Prymids.
Once all of the Prymids are destroyed, the Ancient Minister begins to get worried and sends down Petey Piranha as a Plan B. Petey succesfully knocks Mario into the distance with a canonball and captures Zelda and Peach, all while the Ancient Minister is starting the countdown to the Subspace Bomb. Kirby, noticing he's the only one left, begins to fight Petey Piranha. Then the second level begins where I believe the fight is Kirby vs Petey Piranha. The fight ends either when 3 minutes are up and the bomb detonates, or when Kirby saves one of the princesses. Then, the story branches out from there depending on who you save. This is a random idea of how the branched storyline might go:
Zelda:
Kirby manages to save Zelda, but Petey Piranha flies back into the Halberd with Peach. Kirby and Zelda watch Petey fly away, but then realize that the bomb is about to explode. They rush over to the bomb to stop it, but it's too late. Zelda grabs Kirby and teleports them both out of the arena and into the surrounding desert, where they watch the arena explode in subspace and the Halberd get away. They both then decide that they need to find Mario, and use him to help save Peach. The following level is a sidescroller with them both searching for Mario in the desert. You can swich off between Kirby and Zelda. Either that, or the story switches to Link and Yoshi watching the Halberd get away. OR, the story switches to Pit being told what's happening by Palutena.
Peach:
The same thing happens with the Zelda storyline, except Zelda is the one being kidnapped. Instead of them teleporting out of the arena though, Peach uses her magic parasol to fly up to the Halberd and latch on without the Ancient Minister knowing it. Kirby and Peach climb into the ship, and the following level is a sidescroller through the inside of the Halberd to find the cockpit and defeat the Ancient Minister. Something happens along the way though, and the two are dropped down from the Halberd into the forest or something. Either that or the story switches to Link and Yoshi, or it switches to Pit. Maybe with a Link storyline, he sees Zelda being captured and goes to pursue the Halberd? We won't know until Sakurai tells us...lol.