I bought the Wrath of the Lamb DLC, but the Cathedral isn't unlocked yet. How is this unlocked? Is it because I haven't beaten the Sheol with all the characters yet?
You don't need to beat Sheol with all of the characters to unlock the Cathedral, it's available from the beginning.
Three situations are possible here:
the DLC didn't install correctly. Can you see the new enemies, bosses and basement maps? You should have already encountered at least some spiders. If you didn't, there's been a problem downloading the DLC, and you'll have to reinstall the game. Backup your savegames to be sure you don't lose anything, remove your local data and redownload them. This should do the trick.
you beat It Lives and a Demon room appeared. As I've experienced, if you get a Demon Room after beating It Lives, only the trapdoor to Sheol will appear in the main room. The entrance to the Cathedral will be in the Demon Room/Chapel.
you didn't notice the entrance. The first time I almost missed it. If you beat It Lives without a Demon room spawning, you'll get a trapdoor to Sheol and a beam of light that will bring you to the Cathedral. If you headed straight to the trapdoor, you may have not noticed the beam of light coming from the Heavens.