Williams is in the quarry tower, in the south east region of Broken Valley. The first time you approached the quarry (south of the bandit camp) there was a cutscene conversation with a miner, and then the main entrance was blown up. If you tried to enter you were warned they were too strong for you, but the opponents outside were manageable; inside the tower the Black Ring opponents were a much higher level (in the original release of D2:ED you can still enter early, if you wish; in DKS the tower is locked until after you have the battle tower).
Once you have the key, the entrance to the mine is just south east of the tower (a short flight from the tower, in the direction of one of the walls), and should be marked on the map.
BTW, you can also walk/fly to the fjords from the far south west in Broken Valley, rather than using the portal in Stone's flying fortress.