There is a bit discussion where Rand's new sword Justice (apparently BS and Maria confirmed the sword's nature) was exactly found.

Apparently Rand got it some time between the capture of Semirhage and the first chapter of TGS at the manor in Arad Doman:
"This building was one in a long line of manors, estates and other remote hiding places Rand had used during the last few weeks. He'd wanted to keep moving, jumping from location to location, following the failed meeting with Semirhage. He'd wanted time to think, to consider, and hopefully time to confuse the enemies that might be searching for him. Lord Algarin's manor in Tear had been compromised; a pity. That had been a good place to stay. But Rand had to keep moving."

Rand tells in TGS, ch.1, about the sword:
"He fingered the cloth-tied hilt. The weapon was long, slightly curved, and the lacquered scabbard was painted with a long, sinuous dragon of red and gold. It looked as if it had been designed specifically for Rand — and yet it was centuries old, unearthed only recently. How odd, that they should find this now, he thought, and make a gift of it to me, completely unaware of what they were holding..."

And in ch.37: "He stood, reaching for the sword which leaned against his clothing chest. The black scabbard, with its lacquered red and gold dragon, sparkled in the light. Such a strange weapon those scholars had found beneath the submerged statue. The sword felt so old."

Finally, BS said at a signing regarding the location where the sword was found: "In water, under a statue, not near Falme".

One idea which was suggested is that Justice was found beneath the statue of Hawkwing in the abandoned stedding, where Perrin & Co. camped in EotW, ch.29. In this place Hawkwing planned to built his new capital.

Against this idea speak the following reasons:
The statue isn't submerged or doesn't stand in water. There is only a little pond nearby. It also doesn't make that much sense that scholars suddenly began to dig out this statue in the middle of nowhere. Since the statue was created during Hawkwing's lifetime, where he as far as we know still used Justice, it doesn't seem likely that someone could put the sword later under his statue. There is no reason why the (probably) Andoran scholars would give the sword as a gift to Rand, since their ruler is Elayne; Rand wasn't seen in Caemlyn for some time. Finally, one can hardly understand that scholars, who dig in a stedding that was supposed to become Hawkwing's capital and found under his famous statue an old sword, would be "completely unaware" that they might have found Justice.

Another famous statue we know is the male Choedan Kal near the village Tremonsien in Cairhien. We know that there is an excavation and scholars from Cairhien might be involved now. It also makes sense that those scholars would give the sword as a gift to Rand, since he is their ruler and founded their Academy. Rand or one of his messengers might also have visited Cairhien not long ago to get troops, etc., and during this trip the sword might have been given to Rand. On the other hand, the male Choedan Kal isn't submerged; there is no water nearby, as far as we know. Plus, the Choedan Kal was buried very deeply in the ground, probably since the Breaking. One can hardly imagine how someone could put Justice there.

We definitely know that Rand visited Tear between KoD and TGS, ch.1 (Elayne notes this in KoD). Therefore I think the most likely - although quite dry - conclusion is that the sword was simply found in Tear or near Tear in water (the sea is close to Tear) by some scholars under a possibly unimportant statue (which certainly can't be linked to Hawkwing, because otherwise any scholar should get the idea that the sword might be Justice) and later given as a gift to their ruler Rand, when he visited Tear.

Alternatively the sword might have been found in the other countries ruled by Rand, namely Cairhien or Illian.

IMO, the fact that the sword was found under water indicates that the - apparently leather - scabbard was made anew with the dragon on it, after the scholars found the sword (if it is OP-wrought, it wouldn't rust in the water). Otherwise the sword and scabbard must have been in a completely locked chest.

A final question is, who hid Justice there? The Guide tells that "in early summer of FY 994, Artur Hawkwing was stricken by a sudden illness and went into a precipitous decline. For much of the next month he was fever-ridden and delirious, often shouting for his sword, Justice." Then Hawkwing died.

This could indicate that Hawkwing had already lost Justice at this time; maybe Justice would have even prevented his decline? We know that Ishy manipulated Hawkwing, so maybe he took the sword and hid it (though if Ishy wanted to hide Justice very well, why not simply take it to the Blight or SG?). In any case, it seems clear that Hawkwing himself didn't hide Justice under the statue, but that either Ishy or some (former) confidant of Hawkwing, who maybe didn't want that Justice might fall in the hands of someone else.

However, probably Rand's ta'veren brought Justice out again at the right time.