How does Barbossa come to know that Calypso is bound in Tia Dalma's mortal flesh?

Because she had struck a bargain with him. Quoting the Wikia:

By the time the Black Pearl reached the coast of Shipwreck Island, Barbossa stood on the ship's forecastle, conversing with Tia Dalma, regarding their bargain. The mystic accused him on intending to betray her and therefore reminded him on that he was brought back from the dead by her power, and also, demonstrating her abilities by briefly decomposing Barbossa's right hand, cautioning him of his fate should he fail to keep his end of the bargain. Barbossa in turn reminded her that she, secretly the goddess Calypso, was the one who needed him; she resurrected Barbossa so he could help retrieve Jack Sparrow from Davy Jones' Locker and summon a meeting of the Brethren Court, since only the nine Pirate Lords had the power to free Calypso. To avoid the risk of the goddess reaching an accord with someone else, Barbossa ordered Pintel and Ragetti to lock Tia Dalma in the brig. Barbossa remained on deck, glancing at his right hand while contemplating his debt.

The Wikia also provides the relevant dialogue:

Barbossa: "I do not renege on a bargain once struck. But we agreed on ends only. The means are mine to decide."

Calypso: "Caution, Barbossa. Do not forget it was by my power you return from the dead. Or what it mean if you fail me."

Barbossa: "Don't you forget why you had to bring me back. Why I could not leave Jack to his well-deserved fate. It took nine Pirate Lords to bind you, Calypso. And it'll take no less than nine to set you free."

Although to be honest the same Wikia page somewhat contradicts this in an earlier paragraph:

With the death of Hector Barbossa, the Pirate Lord of the Caspian Sea, came a prime opportunity. Tia Dalma/Calypso needed all the Pirate Lords in order to assemble the Brethren Court, so they could release her from her human bonds. And so, through undetermined circumstances, she resurrected Barbossa from the dead and tricked him to summon a meeting of the Brethren and retrieve Jack Sparrow, who was taken to Davy Jones' Locker by the Kraken.

It seems odd that she had to trick Barbossa into doing what she needed, when his task was pretty specific: rescue Jack Sparrow and convene all the Pirate Lords.

Thus the exact circumstances of their deal remain unresolved.

Why the other Pirate Lords didn't recognize her seems to be a plot hole as well. Calypso does not seem to have powers to have changed her appearance, so her guise as Tia Dalma does seem flimsy.

As far as why Barbossa recognizes Tia Dalma, her deal to bring him back seems to cover that aspect of the story.

Why the other pirate lords do not recognize her seems to be most easily clarified by a quote from Sao Feng to Barbossa.

Feng - "The Court has not met in my lifetime."

Barbossa - "Nor mine."

Feng - "And when last it did, my father told me, it ended...badly."

And, according to the wikia:

The First Court consisted of the Nine Pirate Lords who bound the sea goddess Calypso in her human form, on the instruction of Davy Jones, who revealed them secrets from the Journal of the Ancient Seas. They sealed Calypso's fate with Nine Pieces of Eight, so that the rule of the seas would belong to men. The Brethren would convene a further three times before Calypso's eventual release.

All this would point to the fact that the Bretheren are a completely different generation of pirates, and thus would not have seen the original binding of Calypso to Tia Dalma's mortal body.