When going for the first time, take the horse to the Dragons Breath tunnel. Follow the tunnel up and walk along the edge of the lava pool to the door to the tunnel. (-327.21, 84.84, -149.61)
For faster travel next time, make sure you step on the teleportation gear (looks like a big cog) outside the dungeon. This will activate it, which means next time you only have to go to the teleportation gear at the start of Lavastorm inside the Shrine of Thunder.