If you want to leave Whelk a tip for writing this Super Smash Bros Melee guide you can do so here.
Super Smash Bros Melee Walkthrough 2 - Unlock All Stages
Super Smash Bros Melee 2 - Unlock All Stages
Brinstar Depths (Planet Zebes): Play 50 VS. matches. Stages can be unlocked at the same time as characters, so starting a new Melee save file and playing 50 VS. matches will get you Jigglypuff and Brinstar Depths at the same time.
Fourside (Eagleland): Play 100 VS. matches.
Big Blue (F-Zero Grand Prix): Play 150 VS. matches.
Poke Floats (Kanto Skies): Play 200 VS. matches.
Mushroom Kingdom II: Acquire the Birdo trophy. Trophies can be found randomly while playing through the various 1-Player Modes or by spending coins, which are acquired in many ways in both 1-Player and VS. Modes. In other words, just play Melee a lot and it'll turn up eventually.
Flat Zone (Superflat World): Beat Classic Mode with Mr. Game & Watch.
Dream Land (Past Stages): Clear Target Test with all 25 characters.
Kongo Jungle (Past Stages): Beat 15-Minute Melee. The stage's theme actually suggests one of the best characters for completing the annoying mode: Donkey Kong. He can wait in the middle of the stage and use Down+B over and over to kill the wireframes as they land. Fox and Marth can similarly use Up-Tilt attacks (hold the joystick up slightly + press A), and Mewtwo can simply charge his Shadow Ball (B) forever to knock them flying. In all cases, your greatest enemy is random exploding item spawns.
Yoshi's Island (Past Stages): Hit the sandbag more than 1350 feet/400 meters in the Home-Run Contest. Again, the fact that this is Yoshi's area is a hint that he's one of the best characters to use in the Home-Run Contest (see that section for details).
Battlefield (Special Stages): Complete All-Star Mode, which is unlocked by acquiring all the hidden characters.
Final Destination (Special Stages): Clear Event Match 51, which is unlocked by beating the first 50. This screenshot proves that it is in fact possible to play on this stage with characters other than Fox, and perhaps even with items.