At the start of Dead Man's Chest, Jack Sparrow escapes the Turkish prison with the drawing of the key to the chest. But this happens before Bootstrap Bill comes to warn Jack that Davy Jones is out to make good on their deal. Sure, Jack knew this day would come, but he seems surprised and tries to talk his way out of it. Why had he already taken the first steps to get out of his debt to Jones?
This is just my view of it, but it seems that Jack did know that it was about time that Mr. Tentacles would come to collect. It would also explain why he was so keen on getting the Black Pearl back in the first movie. Supposedly, it is one of the few ships fast enough to outrun the Dutchman and maybe even the Kraken.
The Aztec treasure that he searched for could've also been a way to squirrel out of the deal somehow. But when he saw what really happens to those who take the gold, he would have decided that getting to the heart is a better way.
After getting the Pearl back from Barbosa, he went after the key.
Like I said, this is mostly speculation and guesswork based on what I know of the movies. I could be utterly wrong as well.