When King Olly took over the Mushroom Kingdom, he granted life to the Origami Craftsman's six office tools that assisted him in converting Bowser's Koopa Troop into his Folded Soldiers. Using five long streamers to cover Peach's Castle and transform it into the Origami Castle, he had five of the legion stand guard at the endpoints of the streamers with the Stapler remaining in Peach's Castle as his bodyguard. Colored Pencils went to the Overlook Tower to guard the Red Streamer with Olly using his Earth Vellumental powers to raise it high into the air, Rubber Band went to Shogun Studios and the top floor of the Shogun Theatre to guard the Blue Streamer, Hole Punch went to the Temple of Shrooms to guard the Yellow Streamer, Tape went to the Sea Tower in the middle of the Great Sea to guard the Purple Streamer, Scissors went to the newly captured Bowser's Castle which has crash landed in Shangri-Spa, and the Stapler stayed behind in Peach's Castle as King Olly's personal bodyguard.
With the help of Olivia and several other partners along the way, Mario journeyed to the end of each streamer to defeat the legion members and removed the streamer blocking the entrance to the castle.
After Olivia wished to undo her brother's actions, the Legion of Stationery reverted back to being regular office tools.
The Tape, Scissors, and Stapler were all used as "Things" in Paper Mario: Sticker Star.
With the exception of the Stapler, which is based on a dog, all of the Legion of Stationery are stereotypes. Colored Pencils is an obsessed psychopathic artist, Rubber Band is an overly chauvinistic game show host, Hole Punch is a disco dude, Tape is a New York cab driver (even paraphrasing Ratso Rizzo's world famous "I'M WALKIN' HERE!"), and Scissors is a knight like obsessed duelist.
All but one member of the Legion of Stationery have special colors corresponding with the streamer they are guarding: Colored Pencils' case is red, Rubber Band wears blue rubber bands around its waist, Hole Punch has a yellow lever, Tape's dispenser is purple, and Scissors' handles are green.
The only exception is the Stapler which copies the border of the Origami Castle on the map and its warp pipe in the Musée Champignon.