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 (Normal difficulty).
One way to farm for this is to load a later quest (A Shattered Crown 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 something like "Now those are some big mushrooms" or "These mushrooms are quite enormous." This is an homage to the Black Mushroom quest in the original Diablo.