I am only missing the Black Mushroom to have all the ingredients for the "Staff of herding". So I have to try and get it. The problem is it is unclear where it drops. So sources say you find it in Level 1,2 and 4 of the Cathedral in Act I. There are also some pictures of people finding the Black Mushroom outside. What is the optimal way of going about getting this ingredient?
The best place to find Black Mushrooms is (as others have said) the Cathedral Level 1.
The Cathedral is randomly generated, so you'll want to explore Level 1 fully, and if you don't find it, leave the game and return. The Cathedral will regenerate, and you'll have another opportunity to find the mushroom.
If you've passed this area already, the best story checkpoint for this is "Act 1: Part 4 - Reign of the Skeleton King." You'll start in town, so use the waypoint in town to take you to the Cathedral Garden. Walk southwest, through the gate, and around to the front of the Cathedral. Open the door, and descend through the hole in the floor to get to Cathedral Level 1.
Arrowmaster also suggests starting with the quest "The Legacy of Cain," with the stage "Explore Cellar" - if you play through this quest to the checkpoint at the Cathedral, you'll shave a bit of time leaving and re-entering the game.
It has several spawn points throughout Act I, but the most likely spawn point seems to be in Cathedral Level 1. It can spawn on all difficulties, and there's no difference between them, so you're best off blitzing through it on Normal. Your character will comment on the mushroom patch when you're in the room with it.
The room that holds the black mushrooms is as described by the other answerers, but your character does not (or perhaps "no longer") comments on them upon entering the room. As of June 1, 2012 at least, your character will comment on the mushrooms only after you've "looted" the patch, or at least walked nearly on top of it.
Also, I personally found my mushrooms in a room that was absolutely swarming with enemies, so the observation that they are mostly in rooms without enemies is probably true, but not without exceptions.
(I was not allowed to comment upon the answers or comments in question, so I am forced to submit an "answer" of my own.)
As you can see from here the black Mushroom is customarily found on Cathedral Level 1, but it is very rare. You may need to reset the dungeon quite a few times before stumbling upon it. Your best bet would defintley be to clear out every inch of Level 1 then reset the dungeon until you come across it.