You can enter the Black Omen from the Dark Ages, the Middle Ages, or the Present, but it exists outside of time so it makes no difference. Clearing the Black Omen in any Era will remove it from all Eras, and you can't collect any Treasures twice regardless of which Era you collect them in.
This is the longest dungeon in the game, complete with seven (!) Boss fights, and some fantastic Treasure. There are some nasty Monsters in here, but you can Charm great items from many of them. Finishing the Black Omen will leave the party well-prepared for Lavos. That said, you don't actually have to enter the Black Omen at all—it is strictly optional.
Eventually you'll run into Boss Orbs, which are another version of the Rubble/Turret enemies you've seen before. The Boss Orb is basically a normal enemy, and you should kill it first. The Side Kicks are hard to hit but give generous TP rewards. If you haven't learned every Tech with every Character yet, it's relatively easy to do so in the Black Omen.
After some time you'll find a save point and a pair of Nus. One will allow you to exit the Black Omen, and the other will sell some nice potions.
A long while later, you'll run into the Giga Mutant. You can Charm nice rings from both parts of this Boss. The Giga Mutant is virtually immune to Physical attacks, so use magic and elemental Techs to fight it. It will counterattack magic by draining MP, so you'll likely be low after the fight. If so, use a Shelter at the save point before the Boss.
One last save point leads to the final Boss fights, three in a row featuring Queen Zeal and the Mammon Machine. Queen Zeal's first form likes to drop everyone to dangerously low HP. Frog Squash and Dino Tail are very effective as a result.
Next up is the Mammon Machine. It doesn't attack normally, so just beat on it and heal the party from the fight with Queen Zeal. Physical attacks quickly become useless, while magic powers up its eventual counterattack.
Finishing off these Bosses isn't quite the end, though... it's time for all twelve of Lavos's forms! (Yes, really.) Actually, you can stop after 10 if you want. Check out the "Day of Lavos" Area for more information on Lavos.