The wedding of Will Turner and Elizabeth Swann is interrupted by Lord Cutler Beckett of the East India Trading Company, who has arrest warrants for the couple as well as for Commodore James Norrington, for allowing Captain Jack Sparrow to escape execution. Norrington's whereabouts are uncertain, as he resigned after his obsessive pursuit of Sparrow resulted in the Navy's flagship, HMS Dauntless, being destroyed in a typhoon. Elizabeth is imprisoned, but Beckett promises to free her if Will tracks down Jack and brings Beckett Jack's magic compass which points to whatever the holder wants most. Shortly after, Governor Swann tries to escape Port Royal with Elizabeth but is captured. Elizabeth negotiates with Beckett to let her escape to find the compass herself, and she hides aboard a Scottish merchant vessel, the Edinburgh Trader.
On the Black Pearl, Jack reunites with Will’s father Bootstrap Bill, who reveals he is a crewman on the Flying Dutchman, captained by Davy Jones, whom Jack previously made a deal with to raise the Pearl from the depths. Jack must join Jones' crew or be dragged to Davy Jones' Locker by the monstrous Kraken. Will eventually finds Jack's crew on an island ruled by cannibals, who worship Jack as a god, from which they escape. The crew meet voodoo priestess Tia Dalma (Naomie Harris), who tells them Jones’ weakness is his heart, locked within the Dead Man’s Chest. Locating the Dutchman, Will is shanghaied into service while Jones sends Jack to bring him one-hundred souls so his blood debt can be paid. On the Dutchman, Will meets his father, and learns that the chest's key is in Jones' possession. After playing a game of liar's dice against Davy Jones, Bootstrap helps Will escape with the key, but Jones sends the Kraken after him, sinking the Edinburgh Trader.
In Tortuga, Jack hires a new crew, including Elizabeth, and Norrington, now a drunk. All parties arrive on Isla Cruces where the chest is buried but a three-way sword fight breaks out between Jack, Will, and Norrington who all want the heart for their respective goals: Jack wants to call off the Kraken, Will wants to rescue his father, and Norrington wants to regain his life. In the chaos, Jack obtains Jones' heart and hides it in a jar of dirt, but Norrington secretly steals the heart and runs off pretending to lure away the Dutchman’s crew. Jones attacks the Pearl with the Kraken, which devours most of the crew and destroys all but one of the Pearl's lifeboats, but Jack, who briefly fled, returns and wounds it with a net full of explosives.
Jack orders the survivors to abandon ship, but Elizabeth manacles him to the mast so that the crew can escape the Kraken. Jack manages to break free, but is dragged down to the bottom of the sea by the Kraken. Jones discovers his heart is missing and rages. In Port Royal, Norrington approaches Beckett and gives him the heart and Letters of Marque meant for Jack, allowing him back into the navy as well as allowing Beckett to gain control of Davy Jones and the seas. The Pearl’s crew take shelter with Tia Dalma, where they all agree to rescue Jack. Tia Dalma introduces the captain that will guide them: the resurrected Captain Barbossa.
In a post-credits scene, the cannibalistic tribe now worships a dog in replacement of Jack.

Question: How is Norrington allowed back into the Navy?
Answer: Because he brings Beckett the heart.
Alternative answer: He gets the heart and letters of Marque