Sinking into Vashj'ir

Quest starting items in this area:

Kelp'thar forest:
[item=54345]
[item=62138] (apparently doesn't count for the achievement)
[item=53053]
[item=54639] (edit: apparently it did make it to LIVE but some are having trouble getting it (me included))
[item=55186] (edit: apparently it did make it to LIVE but some are having trouble getting it (me included))

Shimmering Expanse:
[item=54614]
[item=62282]

Abyssal Depths
[item=56812]
[item=57118]

For horde: kill one [npc=42114] and you should automatically get Secure Seabrush

For alliance: kill one [npc=42115] and you should automatically get Claim Korthun's End

Guide to Vash'jir Kelp'thar Forest Alliance Quests:

Optional Pre-quests:
A Personal Summons and Eye of the Storm
Either Into the Abyss: or Hero's Call: Vashj'ir

Main chain:
Call of Duty
Sea Legs (At any time, kill a Slitherfin eel to start Once More, with Eeling)
Pay it Forward
Rest for the Weary
Buy Us Some Time & Travelling on Our Stomachs
(Be sure to kill a Sabreclaw Skitterer to get Crumpled Treasure Map which starts Kliklak's Craw)
To Arms! and Stormwind Elite Aquatic and Land Forces
On Our Own Terms
All or Nothing
Better Late than Dead
The Abyssal Ride
Good Deed Left Undone (optional)
Gimme Shelter! (also unlocks A Case of Crabs)
Ain't Too Proud to Beg
(which also unlocks A Girl's Best Friend and A Taste for Tail)
This is a convenient time to do The Horde's Hoard, which starts
from Tattered Treasure Map, dropped by Clacksnap Pincer

Next comes Can't Start a Fire Without a Spark

This allows for the optional quest Nerve Tonic, and the optional Bud Chain:

• 
  
• Oh, the Insanity
• 
  
• Dan, Nunt... Dah, Nunt...
• 
  
• Shark Weak,
• 
  
• Dun-dun-DUN-dun-DUN-dun
• 
  
• A Bone to Pick
• 
  
• Decisions, Decisions
• 
  

Around this time, kill Gilblin Collectors and hope
Lady La-La's necklace drops for Lady La-La's Medallion. There are conflicting reports of what quests are needed for the item to drop.
This is also a good time to kill Gilblingle for waterlogged journal which starts Blackfin's Booty.

The main chain continues:
Ophidophobia
A Desparate Plea
Undersea Sanctuary
Spelunking
Debriefing
Wake of Destruction
(also unlocks What? What? In My Gut...? and Decompression)
Come Hell or High Water (While in naga camp, pick up How Disarming)
The Warden's Time is auto-accepted
Across the great Divide leads to the Shimmering Expanse chain.

Don't forget to group up or come back at 85 for
An Opened Can of Whoop Gnash

Guide to Vashj'ir Shimmering Expanse Alliance quests:

The Vashj'ir quests start in Stormwind with Call of Duty.
The immediate pre-requisite for these quests is Across the great Divide which starts in Kelp'thar Forest .

Initial chain:
The Looming Threat
Backed Into a Corner
Rundown
Silver Tide Hollow

Several side quests are now enabled:
Slippery Threat, Don't be Shellfish, and A Distracting Scent
Also a side-chain:

• 
  
• The Great Sambino
• 
  
• Crabby patrons
• 
  
• Undersea Inflation
• 
  
• Totem Modification
• 
  
• Back in One Piece
• 
  
• Toshe's Vengeance (optinal linking quest)
• 
  

The main chain continues at Toshe Chaosrender
Vortex (optional)
Vengeful Heart
Fathom-Lord Zin'jatar
A Pearl of Wisdom (optional;starts from Luminescent Pearl from the boss)
Nespirah
Making Contact
Slave Labor and Stick it To Them
Capture the Crab
Breaking Through
We Are Not Alone
Body Blows, Hopelessly Gearless, and Still Valuable
Overseer Idra'kess
Waking the Beast (also unlocks A Cold Welcome)
A Powerful Need to Eat
Clamming Up and Art of Attraction plus Odor Coater
Bellies Await
You can do all these simultaneously:

• 
  
• Swift Approach
• 
  
• Caught Off-Guard
• 
  
• A Better Vantage
• 
  
• An Occupation of Time (optional)
• 
  

While killing naga, hope Ancient Elven Etching drops to start Piece of the Past
If you do these quests and haven't already continued on the main chain,
The Call of the Blade will set you back on track.

Main chain continues:
Upon the Scene of Battle [You can actually get this quest a bit earlier]
Visions of the Past: The Invasion of Vashj'ir
Turn to Naga and do:

• 
  
• Reoccupation
• 
  
• The Revered Lady
• 
  
• To the Fathom-Lord's Call and Built to Last
• 
  
• Not Soon Forgotten (ends first vision)
• 
  

Looking Forward
Clear Goals, Not Entirely Unprepared, and Properly Inspired
Swift Action
Fallen but Not Forgotten and Gauging Success
Visions of the Past: The Slaughter of Biel'aran Ridge
As a naga again, complete:

• 
  
• By Her Lady's Word
• 
  
• No Trespass Forgiven and Stolen Property plus Chosen Burden
• 
  
• Setting an Example (optional)
• 
  
• The Culmination of Our Efforts (ends second vision)
• 
  

Losing Ground
Desperate Plan
Come Prepared, Unfurling Plan, and Hostile Waters
Honor and Privilege
Welcome News
Visions of the Past: Rise from the Deep
As a naga, work on

• 
  
• Devout Assembly and Her Lady's Hand
• 
  
• At All Costs
• 
  
• Final Judgement (awards Visions of Vashj'ir Past)
• 
  

If you are missing any of the naga optional quests, you may now talk to Wavespeaker Valoren to get the Blade of the Naz'jar Battlemaiden which allows you to repeat any of the visions

This chain [for this zone] wraps up:
A Breath of Fresh Air (enables The War has Many Fronts link to Deepholm)
Full Circle

The Vashj'ir quests conclude in the Abyssal Depths