HERO-SIDE STORY
The game starts off with Knuckles and Rouge somewhere in a desert area arguing over who owns the Master Emerald (they are NOT on Angel Island). While the two discuss, Robotnik comes and begins to lift the Master Emerald into the air as he plans to take it to his base. Knuckles glides up and shatters it. Robotnik takes off for his base and Rouge follows after declaring that all the gems of the world belong to her. Response: "We'll see about that bat girl." For the first three Knuckles stages, he's just finding pieces of the Master Emerald oblivious to everything else going on (note: Rouge only has one similar stage at this point of the game).
After Aquatic Mine, Knuckles gets out the sewers and conveniently meets Tails and Amy at that precise spot. Robotnik had recently demonstrated the power of the Eclipse Cannon by blowing up part of the moon and gave 24 hours before he'd use it on earth. Knuckles is brought up to speed on that while Tails finds the President so that the group can find out where Robotnik transmitted his message (place: space colony ARK).
Knuckles leads the group to Robotnik's hideout in the desert and after Tails & Sonic get them through, Knuckles is chosen to find the 3 keys to open the door. After finding the keys, you have to fight a ghost called King Boom Boo. Then Robotnik will appear and send his Golem on Sonic. After that battle the group (Knuckles, Sonic, Tails, & Amy) takes one of Robotnik's shuttles into space. The shuttle hits a meteor and the cargo bay opens up and the shards Knuckles found end up in space. Sonic says not to worry, but Knuckles tries to take over the controls so he can get the shards back anyway. The shuttle ends up docking on ARK and it's when everyone is out that they realize that Knuckles is gone. Sonic & Tails make-up their plan to defeat Robotnik and left Amy alone.
Meanwhile, Knuckles is out finding the Master Emerald shards. However, Rouge noticed the shards energy signature when they were lost in space since she was using the main computer in ARK at the time and went searching as well. Both will find some and this will set-up their second meeting of the game, which is also a boss battle (similar to the Knuckles/Sonic boss battle of Sonic Adventure). The two will be standing on opposite sides of a beam that's over a pool of lava and they'll start arguing again. Rouge will slip and fall, but she doesn't fall far since Knuckles will save her. She gives Knuckles her shards and he restores the Master Emerald. They both then go their separate ways.
Tails manages to do his part before Robotnik captures Amy, causing Sonic & Tails to have to go back for her. Sonic is last to arrive and is carrying Tails' chaos emerald with him (actually, it's the "fake" one Tails made) that Robotnik wants Sonic to give him in exchange for Amy. When Sonic gets to the middle of the room a capsule encloses around as Robotnik claims that he's not going to be fooled by a fake emerald. Robotnik fires the capsule out of ARK and it explodes. Tails, partially fired up by Sonic telling Tails to take care of things, fights Robotnik.
Elsewhere on ARK, Knuckles is walking around when he senses some kind of energy. After a blinding flash, Sonic is on the ground. Knux helps Sonic up while he explains that he was able to use Chaos Control that he's seen Shadow use with the fake emerald since it has the same properties of a real emerald. Sonic plans on doing his part of Tails' original plan and runs off after asking Knuckles to check on Tails and Amy for him. After the last stage, Sonic meets up with Shadow who's surprised Sonic survived. They have a little chat that reveals respect between the two and then Sonic fights Shadow. After winning, Sonic "slam dunks" the fake emerald into the cannon before it fires. The fake emerald explodes when exposed to the real emeralds (as it was supposed to), destroying the cannon.
LAST STORY
Robotnik is in the control room wondering why the cannon won't fire. Then something appears on the screen surprising him.
Sonic & Knuckles enter the main gathering room when they notice some strange vibrations. Rouge arrives and tells them that she got a call from her boss (Rouge is a spy working for the government & her boss is the President) who told her that the colony is falling toward earth. Then something appears on the screen and the five (Tails & Amy are there) turn to watch.
Everyone on Earth gets the same transmission, which is a message recording by Gerald Robotnik, the grandfather of the "current" Robotnik. Robotnik enters the gathering room with the others and gives Rouge Gerald's diary which reveals the following: Gerald was doing research on ARK when the government came to shut down his work on the ultimate life form. People were killed when it was shut down, including Maria, his granddaughter. Gerald lost everything and went insane, but managed to finish his project Shadow which he knew would one day bring destruction to the humans who'd taken away everything from him. Robotnik released Shadow in hopes to take over the planet, but Gerald meant to destroy everyone. Robotnik & Tails figure out what needs to be done (stop the chaos emerald radiation), but don't know how. Rouge remembers that Knuckles had mentioned to her earlier that the Master Emerald can neutralize the emeralds, so a plan is made. The final stage of the game is a 5-player stage. Start as Tails, then Robotnik, then Rouge, then Knuckles, and end it as Sonic.
Amy is mad at being left alone again when she finds Shadow. Amy begs him to help the others and at first he ignores her pleas. However as Amy keeps talking, Shadow sees images of Maria and agrees to help.
Sonic & Knuckles are at the core of ARK (which looks very similar to the Master Emerald shrine from SA) when they're met by the Biolizard, the prototype of the ultimate life form (boss #1). Shadow arrives then and says that he'll take care of it while they stop the emeralds. Shadow fights the Biolizard. While that happens, Knuckles will recite the same incantation Tikal did in SA to get the Master Emerald to neutralize the emeralds. Shadow will join them and the Biolizard will disappear seemingly using chaos control. Suddenly ARK starts moving again and Knuckles wonders why. Robotnik over the intercom reveals that the Biolizard merged with the space colony and is trying to make sure it crashes on Earth, which would destroy the planet. Sonic & Shadow will both use the seven chaos emeralds to go "Super" and confront the Final Hazard (boss #2). After defeating Final Hazard, they will use chaos control to get rid of the last remains of the prototype. While they're doing that, Shadow has memories of Maria again and at the end you see him falling towards Earth.
Sonic will join the others on ARK and when Rouge asks about Shadow, Sonic will give her Shadow's armband. As the beginning credits roll, Robotnik & Tails have a chat, Knuckles & Rouge will have their first & currently only real civil chat, and Amy will talk to Sonic, who'll say that they should all get back to Earth. Sonic is the last to leave and says "Sayonara, Shadow...the Hedgehog." At the end of the credits is a picture of Earth with Shadow on it.