After taking the Stone in Tear, Rand spent a lot of time reading everything he could to help guide him. For example, he learns about the doorway to the snakes and foxes that way:
"A book told me," Rand said calmly. He sat down back on the edge of a
crate that creaked alarmingly under his weight and crossed his arms.
All very cool; Mat wished he could emulate it. "A pair of books, in
fact. Treasures of the Stone and Dealings with the Territory of
Mayene. Surprising what you can dig out of books if you read long
enough, isn't it?
Rand has also learned that the A'iel are the "People of the Dragon", and he is the "Dragon Reborn". It's no small leap from that to him reading anything he can find on their prophecies and understanding he must go to Rhuidean. (The A'iel dreamwalkers, of course, dreamed of the need to be there - Amys knew that Rhuarc would be coming.)
When Rand arrives at Rhuidean and requests permission, he does so in "an ancient form," suggesting it probably came from a book (note, any Lews Therin Telamon memories would have predated Rhuidean, so it couldn't come from there):
He made an odd bow; left foot advanced, left hand on knee, right hand
outstretched palm upward.
"By the right of blood," he said, "I ask leave to enter Rhuidean, for
the honor of our ancestors and the memory of what was."
Amys blinked in evident surprise, arid Bair murmured, "An ancient
form, but the question has been asked. I answer yes."
Mat asks, and is refused, but Rand says that the permission granted himself (Rand) will also cover Mat as Mat is going with Rand. They debate, but the fact of the matter is, they're already hoping/fearing/assuming that Rand is the promised one who will change everything, so to have them waffle about and choose change is not that surprising: (emphasis mine)
"It is not permitted," Melaine said sharply, her long redgold hair
swinging as she shook her head. "You have no Aiel blood in your
Rand had been studying Mat all this time. "He comes with me," he said
suddenly. "You gave me permission, and he can come with me whether you
say he can or not." He stared back at the Wise Ones, not defiantly,
merely determined, set in his mind. Egwene knew him like this; he
would not back down whatever they said.
"It is not permitted," Melaine said firmly, addressing her sisters.
She pulled her shawl up to cover her head. "The law is clear. No woman
may go to Rhuidean more than twice, no man more than once, and none at
all save they have the blood of Aiel."
Seana shook her head. "Much is changing, Melaine. The old ways..."
"If he is the one," Bair said, "the Time of Change is upon us. Aes
Sedai stand on Chaendaer, and Aan'allein with his shifting cloak. Can
we hold to the old ways still? Knowing how much is to change?"
"We cannot hold," Amys said. "All stands on the edge of change, now...