The Black Mushroom is an item used to craft the Staff of Herding to gain access to Whimsyshire. It can be found on Cathedral Level 1. One way to farm for this is to load a later quest in Act I and take the Cathedral Gardens Waypoint then proceed through Leoric's Passage to Cathedral Level 1. The mushroom is rare and you may need to remake multiple times before finding it. To do this, leave game then click "Resume Game". Enemies should respawn indicating the level has been reset, and you may find the mushroom.
The item will be in a patch of lightly glowing violet mushrooms, when the mushroom patch is clicked the patch will make a sound like an opening chest. When the node it spawns from is clicked, you hear a male voice utter "woah." After picking it up, the character will state, "These mushrooms are very large." This is an homage to the Black Mushroom quest in the original Diablo.