Heartsbane is a two-handed Valyrian Steel sword wielded by Randyll Tarly. You can find the sword from ACOK 2.1 onwards.
Acquisition
You can get Heartsbane by joining the army of Lord Randyll Tarly and fighting in a battle as his soldier - you must wait for his death at hands of enemy, or kill him personally with a ranged weapon. Then, you just have to pick the sword from the ground - after battle it should be in your inventory. It works only, when you are soldier in his army - you can't get the sword if you fight against him, or as his ally.
Another way to get the sword is to take Randyll prisoner. Just talk to him from the party screen and choose the option to take Heartsbane. This action will lower your relation with him to -100, your renown by 25 and honour by an unspecified amount (3?).