In this guide, I've listed all the locations of the power-up Mushrooms. (The only worlds with only one Mushroom are 2-1 and 6-2.) If I put something like "Where you find the Potion," that means just throw down the Potion when you get it, enter the door to Sub-Space, and you will find the Mushroom (if you've strayed too far, you may not be able to get to it in Sub-Space).

World 1

1-1
If you don't get the 1-Up by the second POW Block, you can get it from the first of three clumps of grass above you, before the next waterfall. For a shortcut to Birdo, go in the first door in the level, climb the vine, then run and jump over the waterfall to your left. Throw down bombs to open the way to the door. When outside, go left over the wall, and there's Birdo.
Mushroom #1: Where you find the first Potion.
Mushroom #2: Where you find the second Potion.
Birdo: When he spits an egg, jump on it, pick it up, and throw it back at him. Three eggs will put him down for the count.

1-2
Wait until Pidgit swoops down, then jump on top of him. When he flies to his right-most spot, pick him up and throw him off. Before the magic carpet fades away, fly to the right and over the pit.
Mushroom #1: Where you find the first Potion.
Mushroom #2: Inside the first door, climb the ladder. Use the last two clumps of grass on the right to Bomb out the wall on the far right. The Potion is the grass touching the ladder on the right. Pull it out, then walk to the right until you see the wall you just bombed out. Enter Sub-Space; the Mushroom will be at ground level.

1-3
Inside the building, go all the way up to find the Key, then drop all the way down. At the part with three chains side-by-side, drop down and veer as far right as you can. You'll avoid the spikes and find the locked door.
Mushroom #1: Where you find the first Potion.
Mushroom #2: Take the second Potion to the other side of the water on the left. The Mushroom will appear on the high platform that had the five ripe veggies in a row.
Warp Zone: Take a Potion past the rust-colored brick building, all the way to the vase. Go down the vase while in Sub-Space and you'll warp to World 4-1.
Mouser: Stand under his ledge and pick up (or better yet, catch) the Bombs he throws. Run back underneath the ledge and throw the Bomb on it. Blow up three Bombs on Mouser to defeat him.

World 2

2-1
Mushroom: Where you find the Potion.

2-2
Mushroom #1: When you find the first Potion, take a few steps to the right.
Mushroom #2: Where you find the second Potion.
Birdo: Watch out -- this Birdo spits fire along with eggs. Bring a Mushroom Block with you for an extra attack.

2-3
Mushroom #1: Take the first Potion all the way to the left.
Mushroom #2: Go in the door up high on the red hills. The Potion is the first clump of grass to the right of the door. Enter Sub-Space in that room, and you can't miss the Mushroom.
Tryclyde: Hit him with three Mushroom Blocks. Not too hard, just beware of his fire when you go for more Mushroom Blocks.

World 3

3-1
Throw Pidgit off his carpet and fly straight up the middle of the screen to reach a vine to the next part. At this point, if you are using Princess Toadstool, get off the vine and go left. Jump left over the pit to find a secret door. Bomb out the wall, then continue up and left and you'll find Birdo.
Mushroom #1: Where you find the next Potion after the Warp opportunity.
Mushroom #2: Go down the ladder that leads down to five clumps of grass, pull out the Potion (the first clump) and take it as far left as you can go. Enter Sub-Space, then quick climb the ladder to get to the Mushroom.
Warp Zone: Start the stage, then go in the door. Drop down the next pit, and try to stay in the middle of the screen. You'll find a door at the bottom of the water fall. In that room, pull out the Potion (the tenth clump of grass) and take it all the way to the right. Go down the vase while in Sub-Space and you'll warp to World 5-1.

3-2
If you use Princess Toadstool, you can skip a good portion of the stage by jumping left over the pits "underground."
Mushroom #1: Where you find the first Potion.
Mushroom #2: In the "underground" part, go as far left as possible. You will eventually come across an area with four clumps of grass and Porcupos underneath two bomb-able walls. Pull out the Bomb (grass on the far left) and blow up the bomb-able wall on the right, because the Mushroom is going to be under that in Sub-Space. The Potion is the clump of grass on the far right.

3-3
Mushroom #1: When you find the first Potion, go left a few steps, then enter Sub-Space.
Mushroom #2: In the rust-colored brick building, take the Potion all the way to the left. Throw it between the locked door and the ladder. Enter Sub-Space and quick go up the ladder to the Mushroom.
Mouser: Same as in 1-3, except this time it takes five Bombs to blow him up.

World 4

4-1
Mushroom #1: Where you find the first Potion.
Mushroom #2: When you find the second Potion, go left a few steps, then enter Sub-Space.

4-2
Mushroom #1: The first Potion is on the left-most whale. The Mushroom is where you find the first Potion, on the whale's tail.
Mushroom #2: This is a hard one to get! After you take the Rocket up to the next part of the stage, a Potion is in the next clump of grass. Throw the Shy Guy off the Autobomb, pull out the Potion, jump on the Autobomb, then duck. Keep ducking throughout the ride over the spikes. At the end of the spikes, jump to the platform with the door, and enter Sub-Space. The Mushroom is right there.
Warp Zone: In the whale part, take the second Potion to the vase. Go down the vase while in Sub-Space and you'll warp to World 6-1.

4-3
When you see Birdo, don't kill him! Get around him and go to the edge before the water. When Birdo spits out an egg, jump on top and ride it across the pit.
Mushroom #1: Take the Potion by Birdo all the way to the left of the stage, then enter Sub-Space.
Mushroom #2: Take the second Potion to the left, then use the clouds to get on top of the castle wall. Jump your way to the right as far as you can, because the Mushroom will appear on the right-most platform on the second castle structure.
Fryguy: After you hit him with three Mushroom Blocks, he splits into four little fireballs. The safest place to be here is on the top platform, because the little fireballs can't jump up that high. Smash 'em all with Mushroom Blocks then move on to World 5.

World 5

5-1
Mushroom #1: Where you find the second Potion.
Mushroom #2: At the end of the "fish-jumping" part, use the logs to get up above the area where the exit door and third potion is. Drop down the second tunnel, pick up the Mushroom Block. This clears the tunnel for the Mushroom in Sub-Space.
Birdo: Try to get both Mushrooms, because this Birdo is tough! He only spits fire, and you have one Mushroom Block to use as a weapon.

5-2
Mushroom #1: Go down the vase and bring the Potion back up with you. Go a few steps to the right of the vase and then enter Sub-Space.
Mushroom #2: Get the Potion again from the vase (the items reset), and go to the right, past all the Hoopsters, and throw it down on the platform with three clumps of grass.

5-3
This stage is a toughie! Expect to lose a few lives here.
Mushroom #1: Where you find the second Potion (the first clump of grass in the group of five).
Mushroom #2: After the logs, at the part with the ladder going down, let the Bob-ombs blow up that first bomb-able wall. This opens the area where the Mushroom is located in Sub-Space.
Warp Zone: Use Luigi. At the start of the stage, climb the ladder up, then power jump (hold Down for 5 seconds then jump) up to the vase. Get the Potion from the clump of grass on the right. Go down the vase while in Sub-Space and you'll warp to World 7-1.
Clawgrip: Grab the rocks he throws, and throw 'em back at him. Hit him with five rocks to defeat him. Keep in mind that you can't catch the rocks like Mouser's Bombs.

World 6

6-1
In the room with all the vases: The third vase from the left has a 1-Up Mushroom in it, and the fifth vase from the right has a Key.
Mushroom #1: Go down the first vase and bring the Potion up with you. Throw it on the bones resting on the quicksand. Enter Sub-Space, watch where the Mushroom drops, and quickly pick it up before it sinks completely into the quicksand.
Mushroom #2: Take the second Potion as far right as you can -- you should come to a door. The Mushroom will be above that door in Sub-Space.
Birdo: This Birdo only spits fire, but you have three Mushroom Blocks to use...

6-2
Ride the Albatoss flying to the right to get over the huge gaps. Keep your power jump ready at all times; there are some tall obstacles to clear. If you stop to get the Mushroom, you may lose your ride...
Mushroom: Where you find the Potion.
Birdo: What is it with the Birdos in World 6? They only spit fire! You're probably used to killing bird-brain with Mushroom Blocks by now anyway.

6-3
Get up that ladder to start the stage, then go left onto the quicksand. Sink down until you're below the wall. Move left and keep jumping until you get to the other side. Enter the secret door, walk over some clouds to the pyramid, and then you've found Birdo! That was a lot quicker than climbing all those vines, eh?
Mushroom #1: Count the cacti! Take the Potion at the beginning, then drop it on solid ground when the fifth cactus is visible.
Mushroom #2: Inside the "cave" or whatever, get on the upper level, bomb through three walls, then bomb through the next bomb-able floor. (Tip: When you are bombing the walls, pull out the grass right next to the wall so you don't accidentally pull up the Potion.) Now, pull up the Potion, drop through the floor that you just cleared out, and then enter Sub-Space. The Mushroom will be right next to you.
Tryclyde: Make a wall of two Mushroom Blocks on the edge of the upper platform. (This wall will snuff 99% of Tryclyde's fire.) Go down and get a Mushroom Block, then get on top of your makeshift wall and throw it at Tryclyde. Repeat. You've got at least five good chances to hit him three times to defeat him.

World 7

7-1
Anytime after you climb the ladder to start the stage, you can jump on an Albatoss and ride it left. You'll find a Rocket which leads to another part of the stage.
Mushroom #1: Bring the first Potion back to the white platform with the green top. Enter Sub-Space and the Mushroom is right next to you.
Mushroom #2: Where you find the second Potion.

7-2
There are two paths to Wart, but here's the shortest way: When you enter the castle, go all the way to the right and up the chain. You'll go up again, into a tall chamber with a bunch of Sparks. Stay on the right side as you go up. (If you want a Mushroom, stay on the left side as you go up. After you get the Mushroom, you'll have to backtrack.) Go in the door at the top of the chamber. In the next room, go all the way to the right and down the chain. In the next room, beat Birdo for the Key. Take the key and go through the door, go left, and you should now be at the locked door. This leads to a battle with Hawkmouth, who guards Wart's room.
Mushroom #1: Where you find the first Potion.
Mushroom #2: Where you find the second Potion.
Wart: Catch the Vegetables that shoot out of the tubes and hit Wart with them when his mouth is open. Six hits and he's down for the count!