The hythloth entrance is in Fel only at the end of level three in the small room just by the stairs down to level four.
The Fire Isle Volcano entrance is Trammel only, you will need a boat to sail to the Underworld entrance and a pvm quest will let you into the Abyss.
There is also a quest from Ter Mur to enter the Abyss, and an entrance in the lower level of Deceit in Fel; a little door in a small cellar area of the floor before you get to the main lich lord room.