Oh my. What a silly question. Well... let me see here...
This
May
Have
A
Spoiler
Or
Two!
You get to it Post-Spellhold. If you took the portal out of the Dungeon, you go right to it. If you didn't then you sidetrack through Sahaugin City and THEN you go to the Underdark!
BTW, it is UNDERGROUND. UNDERNEATH THE OCEAN!
Hope that helps ya!