I am answering your question as if it was for a science fiction story instead of a fantasy story. Realism in many parts of the setting certainly doesn't harm a fantasy story.
One problem with a black moon is that the Moon of Earth is made of very dark material, slightly darker than coal, and yet shines silvery white when seen from Earth because of the intense sunlight falling on it and reflected to Earth from it, and the contrast with the light less black of the night sky around it.
Another problem with a black moon is getting the background nebula to be bright enough to be brighter than the moon to make the moon look black by contrast.
If your television or monitor screen is turned off, you can see that it's surface is somewhat lighter than pure black. But when the screen is on black parts of a picture appear to be pure black, because the contrast with lighter areas of the screen makes them seen darker to your eye and brain.
Nebulas are considered to be very bright and opaque because commonly seen photographs of them are made with large telescopes and with hours-long exposures, thus capturing many thousands or millions of times as much light from them as you see if you look at them through small telescopes. Actually nebulas tend to look much dimmer and more transparent to the eye than in most photos.
So your solar system should be very close to a nebula or maybe inside it to make the nebula look brighter.
And maybe there is another star in your solar system that emits a lot more invisible ultraviolet and even X-rays than the star your planet orbits. The atmosphere on the planet would shield the surface of it from those rays. And those invisible rays from that star would excite the gases in the nebula and make them emit lower energy light in the visible spectrum, thus making the nebula seem very bright at such a relatively close distance.
A planetary nebula is a shell of glowing ionized gas emitted from a red giant star. Planetary nebulae are usually about one light year, or about 63,241 Astronomical Units (AU) in diameter. So a planetary nebula would cover a large portion of the sky if your planet's solar system and the star that emitted the planetary nebula happened to pass unusually close, within a few light years. According to calculations three stars have or will pass within one light year in a six million year period centered on today, and four more have or will pass within two light years.
The planetary nebula would probably look very dim and transparent compared to most photographs you see of planetary nebulae. But it should look brighter than interplanetary or interstellar space, noticeably brighter than blackness. So when a black moon passed in front of the planetary nebula the contrast should make the black moon look blacker.
Maybe the bright "nebula" is actually an outer moon of your planet and the "moon" of your planet is actually an inner moon of your planet. Your planet could be about the size of Earth and have a moon about the size and distance of the Moon, which would thus look about the same as Earth's Moon. And it could have another, smaller moon that orbits much closer to the planet and - if the orbits of the two planets are in the same plane - it might sometimes pass in front of the outer moon.
Because the star of your planet will have many times the diameter of your planet, the shadow of your planet in space will be a cone. A very long, narrow cone, but one that gets narrower and narrower with increasing distance from the planet. Actually it is the umbra, the darkest part of the shadow where all the light is blocked, which is a long tapering cone. Earth's umbra is about 1,400,000 kilometers or 870,00 miles long, and ends in a point.
The penumbra of an astronomical body is a cone which gets wider and wider the father it is from the body and extends forever into space, a zone where some of the light from the source is blocked by the nearer body and some is not.
Because Earth's atmosphere bends light a little, some red light reaches the Moon when it is in Earth's umbra and makes the Moon look reddish. But if the Moon was much closer to Earth, the light would not be bent enough to reach the Moon and the Moon would appear very dark when in Earth's umbra. So you want the moon of your planet to be much closer to the planet than the Moon is to Earth so it is not illuminated by light bent by the planet's atmosphere.
The moon has an orbital period of 27 days, 7 hours, 43 minutes, and 11.5 seconds, or 27.321661 days. And at an average distance of 384,399 kilometers the Earth's shadow is so narrow that during lunar eclipses the moon usually spends about a few hours in the shadow of the Earth, about 1 percent of less of its orbital period.
If your planet is similar to Earth, the orbital speeds at various heights should be similar to those of Earth. Satellites as low as 99 miles above sea level would orbit with a period of 88 minutes. Similarly satellites 35,786 kilometers or 22,236 miles above Earth's equator are in geostationary orbits taking a sidereal day (23 hours, 56 minutes, 4 seconds) to orbit the Earth. Satellites higher up take longer than a day to orbit the Earth.
Artificial satellites in low Earth orbit spend almost half of their orbital periods hidden in the shadow of the Earth and thus invisible. People who watch artificial satellites know that some of them can be seen with the naked eye at night or even sometimes during the day, and keep track of when they are in sunlight and when they are in the dark shadow of the Earth.
So you should want your large, medium, or small moon to orbit very close to your planet so it spends as large a percentage of its orbit as possible invisibly hidden in the umbra part of the shadow of your planet.
Unlike artificial satellites, natural satellites or moons are held together mostly by their gravity, and so will be broken up by tidal forces if they are below the Roche limit of their primary.
The Roche limit of Earth is 9,492 kilometers for an object with the density of the Moon and 17,887 kilometers for an object with the density of an average comet. These are well below geostationary orbit so your planet could possibly have a natural satellite orbiting below geostationary orbit.
And as a general rule you probably want your planet's moon to orbit as close to the planet as possible so as to spend as large a proportion of its orbit as possible invisible in the umbra part of the shadow of the planet. Especially if the bright nebula doesn't surround the solar system but occupies only a part of the planet's sky.
But there is a problem. Tidal interactions with the planet cause moons beyond geosynchronous orbit to move farther and farther away from the planet, while making moons below geosynchronous orbit move closer and closer to the planet and eventually reach the Roche limit and break up. Phobos, the inner moon of Mars, is moving inward and predicted to reach the Roche limit and be destroyed in about 30 to 50 million years.
If your Earth like planet is old enough to have interesting features like a breathable oxygen-nitrogen atmosphere, or multi celled life, or intelligent natives, which should be several billion years old, any moons below geosynchronous orbit should have already spiraled in and been destroyed, while moons just outside geosynchronous orbit should have spiraled out for tens of thousands or hundreds of thousands of kilometers and be much farther out than you want.
So maybe any visiting Earth people may note that the close moon of the planet is just there, but unexplained, like the origin of the close moons of Mars is unexplained.
Or maybe the close moon of your planet was a wandering object that was captured by the planet very recently on a planetary time scale, maybe just a hundred million years or something ago, and was captured at a distance close to the geosynchronous orbit and hasn't had enough time to spiral very far in or out.
Another possibility would be to have instead of a nebula, another nearby planet that reflects the light from their sun.
The "planet" in your story could be an Earth sized moon of a gas giant planet which has the role of the "nebula" in the story. The gas giant planet would probably have many times the apparent diameter of Earth's Moon. The "moon" in your story could be another moon of the gas giant planet that orbits closer in. Sometimes when that inner moon was between the habitable moon and the gas giant it would enter the shadow of the habitable moon and appear black against the illuminated background of the gas giant planet. The shadow of the habitable moon could reach to the inner moon but not to the surface of the gas giant.
Or maybe the shadow of the habitable moon could reach to the gas giant planet and darken a small part of the gas giant planet. But if the gas giant planet has intense auroras in its atmosphere the shadowed part of the planet could glow dimly with the delecate colors of the auroras. The inner moon would have no auroras and would be pitch black when it entered the shadow of the outer moon and covered part of the planet.
This possibility has the feature that the gas giant planet could appear very large in the sky of the habitable moon orbiting it, perhaps the closest of any other possibility to that of Possibility One, a very close planetary nebula.
Or the "moon" of habitable moon could actually orbit the habitable moon, thus being a moon of a moon.
It is possible for a moon to have a moon, but the orbit would be unstable and a moon of a moon would soon escape from the moon into interplanetary space. Soon by astronomical and geological standards of course.
Another possibility would be to have the planet a planet orbiting the star with its moon and the "nebula" another planet in an outer orbit.
In our solar system planets never get closer to other planets than tens of millions or hundreds of millions of kilometers. But in a few other solar systems planets sometimes get much closer than that.
The closest known planetary orbits to each other are in the Kepler-70 system. The orbit of Kepler-70c is about 240,000 kilometers farther out than the orbit of Kepler-70b. So the two planets are only about 240,000 kilometers apart when closest, and Kepler-70c can look five times the apparent size of the Moon in the sky of Kepler-70b. Any moon of Kepler-70b would have to be very close to it.
There is some evidence for a planet orbiting between Kepler-70b and Kepler-70c, but it is unconfirmed.
Potentially habitable exoplanets that are very close together are the four potentially habitable planets of TRAPPIST-1.
The system is very flat and compact. All seven of TRAPPIST-1's planets orbit much closer than Mercury orbits the Sun. Except for TRAPPIST-1b, they orbit farther than the Galilean satellites do around Jupiter, but closer than most of the other moons of Jupiter. The distance between the orbits of TRAPPIST-1b and TRAPPIST-1c is only 1.6 times the distance between the Earth and the Moon. The planets should appear prominently in each other's skies, in some cases appearing several times larger than the Moon appears from Earth.
According to my rough calculations, when TRAPPIST-1e is closet to TRAPPIST-1d it would appear to be about 37.8 arc minutes wide, and when TRAPPIST-1g is closest to TRAPPIST-1f it would appear to be about 40.2 arc minutes wide. The Moon as seen from Earth is 29.3 to 34.1 arc minutes wide.
astronomers consider it highly unlikely for the TRAPPIST-1 planets to have moons in stable orbits.
Assuming that you would want the moon of your planet to orbit at a distance of 10,000 to 50,000 kilometers from the surface of the planet, and that your planet has exactly the same mass and density as the Earth, your planet would have about 58.9 to 1,477.6 times the gravitational attraction on its moon as Earth has on the Moon.
And if you assume that your planet should have at least 100 times as much gravitational attraction on its moon as the outer planet does, the outer planet should have less than 0.589 to 14.776 times the gravitational attraction on the moon as Earth has on Earth's moon.
If the outer planet had the mass of Saturn, the least dense planet in our solar system, it would have 95.159 times the mass of Earth. Thus it would have to be at least 9,515,900 to 47,579,500 kilometers away at the closest approach to your planet. At those distances Saturn with a diameter of 116,464 kilometers would have an apparent diameter of 8.4 to 42.04 arc minutes.
Or you could have a habitable planet with a smaller planet orbiting about 1,000,000 kilometers farther out and a Saturn sized planet orbiting about 6,289,232 kilometers farther than the first planet. When the Saturn sized planet was closest to the habitable planet it would appear to have an apparent diameter of 400 arc minutes or 6.66 degrees, about 11.73 to 13.65 times the apparent diameter of the Moon from Earth. And sometimes the intermediate planet would pass in front of the Saturn sized planet if all the planets orbited in the same plane.
I hope that my 12 possibilities will give you and the others who have answered your question things to think about and discuss.
By the way, if you think it may be a big problem to arrange for a black moon to pass in front of a nebula that is brighter than black, there are been a few science fiction stories and programs that feature a white sky with black stars. The thought of trying to explain and justify that gives me shudders.