At the character screen, click Change Quest.
Under ACT I Chapter 4: Reign of the Black King, select Begin Quest. Click Select Game.
Start the Game. At the Waypoint, select Cathedral Gardens.
Don’t enter the entrance next to the Cathedral Gardens waypoint (That’s Leoric’s Passage). You have to walk west of the Cathedral Gardens waypoint, and past the gates you will see the Tristram Cathedral’s front door. Break the door. Enter the Cathedral Level 1 entrance.
The Black Mushroom is an item that spawns randomly in the Tristram Cathedral Level 1 inside one of those big rooms with two exits — as illustrated below.
There’s a fissure on the ground where the Black Mushroom grows. Hover your mouse over the stack of mushrooms and click it to loot the Black Mushroom.
If you don’t find the Black Mushroom, leave the game and click Resume Game. A random map of the Cathedral Level 1 will spawn. Rinse and repeat until you find the Black Mushroom. The room you are looking for looks like this in the mini-map.
Note: I haven’t confirmed this in Diablo III Retail: In beta, the Black Mushroom used to drop from the Cauldron located within the cellar at Adria’s Hut.