NOTE: This spoiler was sent in by Paul P.
The movie opens by showing a hot dog, bag of popcorn, and a couple of other movie food items dancing onto the screen. It looks very much like something you'd see in an old movie theatre. They get through about half of their routine of dancing and singing when they begin to stop and look nervous. In the background, you can see that they've danced out in front of a pretzel, a nacho, and a few other 'bad' movie foods carrying musical instruments. They stare the 'good' food items down a moment, and the 'good' items back away, before the 'bad' items begin a loud heavy metal song indicating to viewers that bad movie etiquette will result in severe bodily harm to the viewer.
From there we move to what is presumably Egypt, where Shake, Frylock, and Meatwad emerge from the back of a sphinx. I humongous poodle awaits them there, and begins to attack the Aqua Teen Hunger Force. Shake and Meatwad run for a nearby Jeep while Frylock holds the dog off, but the dog eventually catches Frylock, shaking him around in its maw violently and tossing him to land lifelessly by the Jeep.
Shake and Meatwad drive off with Frylock's corpse, and meet Abraham Lincoln, who takes them to his rustic-looking shack, where he plans to revive Frylock. Just as Frylock is revived, however, government agents crash down the door. They begin shooting everything in sight, but the entire gang has gotten away. The agents argue for a moment about whether there are any invisible bad guys in the shack, while the Aqua Teens and Lincoln get away. ("Just because that /one/ bad guy was invisible it doesn't mean they /all/ can do that!")
Eventually the agents catch up with the gang, and it becomes clear that they are after Abraham Lincoln - who is able to travel through time at will - because he is using his power for evil. Time Lincoln, in order to save the Aqua Teens from apprehension, has them board a wooden rocket ship (marked 'Air Force One').
Soon after, Frylock's voice interrupts all of this, and we see that what has just been transpiring is actually Master Shake telling Meatwad the origin story of the Aqua Teen Hunger Force. Frylock explains that this isn't at all how it happened, and that it was all just one of Shake's usual lies.
Master Shake becomes annoyed, and heads off to work out on his new exercise machine, the Insane-O-Flex. He begins dragging the contraption out into the living room, where Frylock tells Shake that he's assembled it incorrectly. It has cables haphazardly strewn about, tied to other parts, making it look more like a pile of exercise machine parts than anything else.
They can't find the instructions to assemble the machine, and so Frylock goes to his computer to look it up online, where they read that the machine is in actuality an immortal device which will bring about mass destruction if assembled. ("Don't ever, ever, ever, ever, ever, ever, ever, ever, ever, ever, ever, ever, ever, ever, ever assemble the Insane-O-Flex.") Frylock begins assembling the Insane-O-Flex.
We then cut to a shot of space, with the Plutonians' ship coming into view. Emory and Oglethorpe hear something in their ship with them, and discover that they are not alone. The Cybernetic Ghost Of Christmas Past From The Future is there with them, and begins explaining to the two aliens the story of the Insane-O-Flex. The machine, when assembled, will exercise a man into a super-being, who will destroy all of the other men. Since one man is not enough to keep the species going, the human race will eventually die off. Emory and Oglethorpe discuss how they might use the Insane-O-Flex for their own twisted purposes, but the Cybernetic Ghost Of Christmas Past From The Future is adamant that they must not. He has even taken steps to prevent it from ever being assembled, by traveling into the past and removing a single screw. The Plutonians point out to him that to get it assembled, someone could just shove a pencil in there.
Cut back to Frylock, who says, "It's done! There was a screw missing, but I just shoved a pencil in there." Master Shake, eager to get buff for the ladies, wants to test it out, but the group notices that when they flip the switch the machine does nothing. Curious, Frylock opens up the back panel and sees that an M-shaped circuit board is missing. Frylock suggests that they get in touch with the person Shake got the machine from to see if they still have it laying around.
Carl, who had bought the machine at a yard sale and had it stolen by Master Shake, is asked the whereabouts of the M-shaped board, but he doesn't know. They ask him where he'd bought the Insane-O-Flex, to see if they could reach *that* person. Carl tells them that it is the Aqua Teens' nemesis, Dr. Weird. (The M-shaped board is shown, and flipped over to show that it is actually a "W".)
We cut to a scene (somewhere hereabouts) where a triangular slice of watermelon is flying about in a ship made from a hollowed-out watermelon along with Neil Peart from Rush. The watermelon slice watches everything transpire and exclaims, "Yes! Everything is unfolding perfectly!"
Dr. Weird and Steve, whose abandoned insane asylum has been bought and is being turned into condominiums around them, are visited by Shake, Frylock, and Meatwad, but have disguised themselves in order to fool the Aqua Teens. Eventually, the Aqua Teens leave empty-handed. Soon after this, we see that who we thought were the Aqua Teens were actually Emory, Oglethorpe, and the Cybernetic Ghost Of Christmas Past From The Future in disguise. They quickly hide down a back alley and take the disguises off as the real Aqua Teens approach in search of the same part. To aid in not being detected, they all begin making out in the shady back alley. Oglethorpe seems to enjoy his kiss with the Cybernetic Ghost Of Christmas Past From The Future a little too much.
The Aqua Teens come to the door, and Steve - Dr Weird's assistant, and again in disguise - says that he's already told them he doesn't know what they're talking about. Frylock catches on, asking what was meant by him saying he 'already told them', and the Aqua Teens barge into the room. Eventually, they retrieve the missing part and head back home.
Back at home, Frylock installs the missing circuit board, but Carl insists that as the rightful owner he should be the first to test out the machine. He sits down, and as it's turned on the machine straps him in and transforms into a huge one-eyed monsterous robot. The robot plays music and begins stomping around, crushing houses and heading toward downtown, all while Carl's strapped-in form is forced to exercise. Eventually, it begins laying large metallic eggs, which will hatch into smaller versions of the machine.
The Aqua Teens, aided by an instructional work-out video, find a way to destroy the machine and save the planet from this destruction. They confuse the robot by playing it some music from Master Shake's new CD "Nude Love", and it destroys itself, freeing Carl, who is now bulging with muscles. Carl finds an equally muscular woman, and they head back to her condo while the Aqua Teens try to figure out a way to stop the newly-hatched smaller robots from destroying the city.
As they are discussing, Frylock begins to tell the origin story of the Aqua Teens. They were created by Dr. Weird - the same mad scientist who created the Insane-O-Flex - along with a chicken nugget who had gone by the name of Chicken Bittle. Chicken Bittle and the rest were created for one purpose, and one purpose only: to crash a jet into a brick wall. Realising that this was silly, Frylock diverted the jet and they eventually make their way to Africa, but while parachuting down to the earth Chicken Bittle was eaten by a lion. The Aqua Teens' appearance frightened away the villagers nearby despite the fact that Frylock had wanted nothing more than to help them. Frylock, feeling guilty for causing the death of Chicken Bittle and for failing to help anyone in Africa, takes Shake and Meatwad to New Jersey to live the rest of their lives. Master Shake and Meatwad ask Frylock why they can't remember any of this, to which Frylock responds that they were too busy playing their Game Boys to notice that any of it had happened. The story told, the group travel to Dr. Weird's Laboratory on the Jersey shore once again to try to find a way to stop the smaller Insane-O-Flex robots.
We then see Carl and the muscular woman he had earlier gone off with. They move into the bedroom where the woman ties Carl to the bed, but it isn't long before she reveals herself to actually be Dr. Weird in disguise, and we realize that they are actually at Dr. Weird's lab. The Aqua Teens eventually arrive, but we see that Dr. Weird has already taken a hunting knife to Carl's muscles and grafted them on to him own body. On the outside.
Frylock and Dr. Weird do battle, and the struggle continues while arguments continue back and forth about who created who. Dr. Weird keeps calling Frylock 'daddy' while Frylock goes on about Dr. Weird having created the Aqua Teens. Eventually, the fight is ended when Frylock uses beams from his eyes to cut Dr. Weird in half at the waist. Dr. Weird falls to the ground, but they all still argue until Shake shoots Meatwad with a shotgun.
In swoops a hollowed-out watermelon ship to land near everyone, and out comes the watermelon slice from the cutscene earlier - identifying himself as Walter Melon - and Neil Peart, drum set before him. Neil's magical drum-playing brings Meatwad back from the dead. Walter Melon then explains that none of their stories are true and that in reality it was he who created everyone. Frylock, who can't remember any of that, protests, and we find out that behind the blue diamond on his back is a VCR. As the tapes can be changed, it would have been easy for Walter Melon to erase his knowledge of their origin and replace it with whatever he wanted.
The origin mystery finally solved, the movie ends with more singing from the rockstar food items at the opening of the movie.