The Star Pieces originate from Star Hill where it was broken apart by Exor when it passed through Star Hill and entered Bowser's Keep. Mario managed to find one without knowing it's real purpose but it was after getting the second Star Piece from Geno where he learned why they are needed. The Star Pieces are needed to help grant the wishes of those who have wished. However, this cannot be done with Star Hill damaged and the Star Pieces are needed to restore it back to full power. Star Pieces are usually guarded by members of the Smithy Gang though others can be found laying around in areas or guarded by other bosses (such as Jonathan Jones).
Blue Star Piece
The first Star Piece is found in the Mushroom Kingdom. After Mario and Mallow arrive back from Bandit's Way after defeating Croco, they find the town overun with Shysters. Mario and Mallow enter the castle where it is taken over by Mack of the Smity Gang. Mario and Mallow defeat him in battle and Mario earns the first Star Piece.
Green Star Piece
The second Star Piece is found deep within the Forest Maze. It was found by an Aero who has given it to Bowyer. Geno arrives and attempts to stop Bowyer from firing Aeros and to hand over the Star Piece but Bowyer doesn't agree to. Mario and Mallow join Geno in the battle where they all fight against Bowyer and win. It is then where Geno tells Mario and Mallow about the importance of the Star Pieces and why he has came from Star Hill to retrieve them.
Orange Star Piece
The third Star Piece is found deep within Moleville Mines. This Star Piece is guarded by Punchinello who actually isn't working with Smithy. However, he does fight Mario and his team hoping to become famous. Mario, Mallow, and Geno all defeat Punchinello and retrieve the Star Piece after it fell from the ceiling thanks to Punchinello's King Bomb.
Purple Star Piece
The fourth Star Piece is found on Star Hill itself. Mario must work his way around the damaged Star Hill to retrieve this Star Piece. It should be noted that this is the only Star Piece in the game where it wasn't guarded by a boss.
Indigo Star Piece
The fifth Star Piece is found deep in the Sunken Ship beneath the Sea. It was being guarded by Jonathan Jones and his gang. After Mario defeats Jonathan Jones, the shark pirate hands over the Star Piece out of respect for Mario's fighting skills. However, as Mario re-enters Seaside Town, the Elder (revealed to be Yaridovich of the Smity Gang) demands Mario to hand over the Star Piece or he'll harm the citizens. Mario hands over the Star Piece and Yaridovich and his clones attempt to get away by taking the Blade. However, the Blade is running late so Yaridovich tires to swim away knowning he would rust. Fortunately, Jonathan Jones and his gang stops Yaridovich saying Mario has won the Star Piece fair and square and leaves the plumber to handle Yaridovich himself. Mario and his team eventually defeat Yaridovich and regain the Indigo Star Piece.
Red Star Piece
The sixth Star Piece is found within Barrel Volcano. It was being guarded by the Czar Dragon. After Mario and his team defeat the Czar Dragon (and its reincarnation), Mario can get the Star Piece. However, just as Mario is about to claim the Star Piece, the Axem Rangers suddenly appear and steal it. Mario makes chase to the Axem Rangers up Barrel Volcano and eventually catches them trying to leave on their airship the Blade. Mario and his team defeat the Axem Rangers and regain the Red Star Piece.
Yellow Star Piece
The seventh and final Star Piece is found in The Factory where it was guarded by Smithy himself. Smithy intened to destroy Star Hill and fill the world with weapons. Mario and his team enguage Smithy in the final battle where they come up victorious. Everyone (Mario, Mallow, Geno, Bowser, and Princess Toadstool) all come out to watch all seven Star Pieces form together and Star Hill is restored. With his mission accomplished, Geno returns into his original form and heads back to Star Hill.