I'm sure there are plenty of people that know of the island that exists below Tanaris, but I was never able to get there before now. I'm at work, but just remembered to post my findings on this from last night, and I'll post an image to go along with this later when I get home if anyone needs one.
It's real simple. With a Death Knight (either in your party or your own DK), have the DK cast Path of Frost so that you can mount on the water. Note, in order to pull this trick off, you'll need an epic land mount.
Follow the path south east (below Caverns of Time) in Tanaris, and exit into the water, following the coast line, all the way down until you reach the zone "Lands End Beach".
Once there, make sure you have plenty of time on the buff (Path of Frost) and go to the southern tip of water just before you hit "Fatigued" area. From here, run directly south as fast as you can, and eventually, you'll reach the island.
The first island is nothing more than a few houses, but there is another island just south of that, that has the pirates on it as well. My next step will be to become friendly with them, if possible, and see if there any other quests there as well.
Note - I do realize that there is a quest to get to this island as well (I think, if I remember correctly, that it's alliance only), this is just another means of getting to the island, which I have never been able to do before now.