The Legend of Videoland is an ancient prophecy in the cartoon continuity of Captain N: The Game Master.
It is mentioned in "Kevin In Videoland" through a booming voice, though the significance of the voice and how it relates to the Legend of Videoland and/or the Ultimate Warp Zone (if at all) is unspecified.
The voice said "Do not give up hope yet, Princess. There are powers beyond those with which you are familiar. The Legend of Videoland foretells of a young warrior...from another land...and shall warp into our world and lead you to victory. He is Captain N: The Game Master. Behold...the Ultimate Warp Zone!"
At this point, the Ultimate Warp Zone opened and brought Kevin Keene to Videoland.
Lana has her own take on it in her narration during the (noncanonical) Season 2 opening theme song: "When my father disappeared, and Mother Brain tried to take over Videoland, our only hope lay in an ancient prophecy that a great warrior from another world would come to our rescue."
No backstory on the Legend of Videoland, nor any further elaboration - such as what qualifies Kevin to be the Game Master or how the Legend of Videoland relates to the Ultimate Warp Zone - was ever established.
In Season 2's "The Big Game," Lana tells Kevin's friends, "Hey, we asked for the best from your world, and the Ultimate Warp Zone chose Kevin as our Game Master!" This statement not only omits any mention of the Legend of Videoland but also is historically inaccurate. No one asked for a hero.