The Long Night and threat of the Others came around 8000 years before Aegon's Conquest. However its rumored/known that Valyrian steel is one of their weaknesses through books and writings in the archives of the Night's Watch. How can they know this if Valyria and by extension Valyrian steel didn't even exist until around 5000 years before Aegon's Conquest. The Others disappeared after the Long Night and the Night's King so how could a weakness of theirs be known if it didn't even exist at the time they were around?
Valyrian steel swords were made using dragon fire, just like dragon glass*. With dragon glass being a weapon known to work against White Walkers, it was quite logical (even if not confirmed) to assume a sword forged in dragon fire would be effective.
Sam Tarly (in the books) read that "Dragon Steel" can kill White Walkers. It's not a stretch to say that dragons existed long before Valyria, and that Valyrian steel isn't the first product to be made with dragon fire.
All things that can kill White Walkers have one thing in common - they are made with dragon fire. Just like Valyrian steel swords.
*according to smallfolk. GRRM said it's infused with magic. It's safe to assume dragon glass has a connection to dragons, since the biggest deposit is on the island where Targaryens and their dragons spent over 400 years. On the other hand, Maesters say it simply came from the Earth. Now keep in mind that this doesn't explain the fact that dragon glass is infused with magic, and also you have to remember that Maesters sought to eradicate both dragons and magic. They fight using lies and poison.
According to The World of Ice and Fire Valyrian Steel first started to come to Westeros properly around 200 years before The Doom but it was already in the Seven Kingdoms before that.
Perhaps in preparation for their crossing of the narrow sea, the Valyrians also established their westernmost outpost on the isle that would come to be known as Dragonstone some two hundred years before the Doom. No king opposed them—and though the local lords of the narrow sea made some effort to resist it, the strength of Valyria was too great. With their arcane arts, the Valyrians raised the Citadel at Dragonstone.
Two centuries passed—centuries in which the coveted Valyrian steel began to trickle into the Seven Kingdoms more swiftly than before—though not swiftly enough for all the lords and kings who desired it. And although the sight of a dragonlord flying high above Blackwater Bay was not unknown, it occurred more frequently as time passed. Valyria felt its outpost was secured, and the dragonlords thus continued their schemes and intrigues on their native continent.
The World of Ice and Fire, Ancient History: The Doom of Valyria
Sam reads about dragonsteel in a book where the last hero killed an other with a blade made of the material. Though it's unclear if dragonsteel is Valyrian steel Sam and Jon seem to think it is.
"The armor of the Others is proof against most ordinary blades, if the tales can be believed," said Sam, "and their own swords are so cold they shatter steel. Fire will dismay them, though, and they are vulnerable to obsidian." He remembered the one he had faced in the haunted forest, and how it had seemed to melt away when he stabbed it with the dragonglass dagger Jon had made for him. "I found one account of the Long Night that spoke of the last hero slaying Others with a blade of dragonsteel. Supposedly they could not stand against it." "Dragonsteel?" Jon frowned. "Valyrian steel?"
"That was my first thought as well."
A Feast for Crows, Samwell I
Note though that when Daenerys pledges a Valyrian steel sword to Ser Jorah Mormont she mentions dragon-forged separately. This could mean that Valyrian steel is essentially just a brand of dragonsteel and so Valyrian steel has never been tested before but different versions of it have been.
She nodded, as calmly as if she had not heard his answer, and turned to the last of her champions. "Ser Jorah Mormont," she said, "first and greatest of my knights, I have no bride gift to give you, but I swear to you, one day you shall have from my hands a longsword like none the world has ever seen, dragon-forged and made of Valyrian steel. And I would ask for your oath as well."
A Game of Thrones, Daenerys X
This alongside the fact that obsidian has been tested and proven against the Others and it is referred to as dragonglass probably gives them enough reason to believe it can kill an Other.
And then he was stumbling forward, falling more than running, really, closing his eyes and shoving the dagger blindly out before him with both hands. He heard a crack, like the sound ice makes when it breaks beneath a man's foot, and then a screech so shrill and sharp that he went staggering backward with his hands over his muffled ears, and fell hard on his arse.
When he opened his eyes the Other's armor was running down its legs in rivulets as pale blue blood hissed and steamed around the black dragonglass dagger in its throat. It reached down with two bone-white hands to pull out the knife, but where its fingers touched the obsidian they smoked.
A Storm of Swords, Samwell I