It's a bit more complex than "a Legend" and has to do with Hope
Did they literally expect a King to eventually return, or was it a hopeful legend, more like the hopes of the Ents that the Entwives would eventually return?
While most people in Gondor probably weren't sure if any Dunedain survived the fall of Arnor, some hoped that their True King's line survived. (RoTK, Appendix A, the Fall of Arnor). That the institution of the Steward survived centuries after an heir might have been found, and that both Imrahil and Faramir readily accepted Aragorn as True King demonstrates the power of this cultural symbol of Hope Fulfilled.
ROTK, Appendix A:
Each new Steward indeed took office with the oath "to hold rod and rule in the name of the king, until he shall return." ... Yet many in Gondor still believed that a king would indeed return in some time to come; and some remembered the ancient line of the North, which it was rumored still lived on in the shadows.
In Real Life, when the last of a royal line falls, a new royal line is established, either by a usurper or from various blood relatives. (Reference = history of European civilization.) Appendix A, RoTK describes a civil war in Gondor -- the Kin Strife, Third Age 1432-1447. When King Earnur later fell in Third Age 1944, his Stewards ruled in his stead. The office of the Steward was an old one: Kings often went to war, and the expectation/hope was that the King would return. This established the deep cultural tradition, based on the hope* of the King returning.
Boromir asked Denethor how much time must pass before a Steward could become a King, if the King did not return. Denethor II replied:
"Few years, maybe, in other places of less royalty … In Gondor ten thousand years would not suffice" (related by Faramir in The Two Towers Book IV, The Window on the West).
Now try to see this through the eye of the author, the role of the Steward. There's more to this than "the words of Appendix A," based on the none-too-subtle themes that Tolkien wove into his magnum opus. (The Red Book of Westmarch handed from Frodo to Sam is properly "The Downfall of the Lord of the Rings and the Return of the King" (p. 307 Book VI, Ch The Grey Havens, Second Edition)).
Hope of the King's return was stronger than a legend or the vain hope of the Ents: it was a cultural touch point, a profound hope* of a people, a belief central to the culture of Gondor for over a millenium. It's not a stretch to say that it was as deeply interwoven into the Gondorian culture as Christian beliefs and symbols were interwoven into Medieval Western and Central Europe's cultures. Tolkien wrote what he knew, and his deep Catholic faith informed his work.
“The Lord of the Rings is of course a fundamentally religious and Catholic work; unconsciously so at first, but consciously in the revision. That is why I have not put in, or have cut out, practically all references to anything like ‘religion’, to cults or practices, in the imaginary world. For the religious element is absorbed into the story and the symbolism. ~ Tolkien, Letters, 172~
The deeply held belief resembles the RL cultural touch point that Tolkien held to be a truth: his belief and Hope* in the Second Coming(return) of Christ (the King of Kings) in Christendom. (I use "Christendom" to cast the point outside of our current cultural setting and to avoid religious debate: LoTR uses the more or less Crusader-era society). Tolkien, a devout and lifelong Roman Catholic, mixed his religion's beliefs, symbols, and values with the folklore and legend of the Norse and English literary and linguistic traditions in which he was expert. While he protested against allegory, and said he didn't use in his own work, his protest is hard to swallow when looking at the structure of the lineage of the Royal House of Gondor and Arnor, and the Stewards who looked after it for centuries -- but we'll use his term, applicability rather than allegory.
The story of the good and faithful Steward who looks over the Master's domain is told in Matthew 25. When Tolkien published the LoTR, most people would "get" the common cultural (Western) reference to the Steward, so it's applicability would resonate.
Tolkien constructed the line of the True Kings of Gondor (and Arnor) from an ancient lineage that bears a striking resemblance to the template used in the Old Testament. The great King (David) established the Kingdom (with no end) of the special people. His line lasts through generations of defeat and turmoil and is revived in Jesus (called King of Kings) even when the line's roots were buried and the people were exiled from their homeland -- which itself was a gift from On High. (Numenor / Gondor mixed, original gift was Numenor from the Valar). Aragorn's lineage passes through the centuries and he emerges unexpectedly, the embodiment of a hope* unlooked for in Gondor. It is a eucatastrophe for the people of Gondor.** (Even if it seems a catastrophe to Denethor).
If this template wasn't a direct decision -- including the symbol of the tree in Minas Tirith with deep roots eventually blossoming in a True King blessed by the Almighty / Valar -- the symbolic theme still stands out.
Tolkien gave similar treatment to the Elves in terms of Gondorian cultural beliefs balanced against their daily lives. The folk of Gondor knew that there were Elves, and from lore knew that years ago Elves and Men made common cause against The Enemy. (Granted, there was fear as well: cf. Boromir's reluctance to enter the Golden Wood, FoTR, Book II, Ch. Lothlorien). When the Elves arrived in Gondor for the coronation of the King, (Book VI, Ch = The Steward and the King) it restores the linkage between legend, belief, cultural memory, and what becomes their new Truth: their hope* is fulfilled by the True King arriving out of legend. Faramir discharges the final duty of the last Steward.
In RoTK(book) during the narrative of the coronation scene, Aragorn is crowned King Elessar, the Elfstone -- all Tolkien omitted was calling him The Anointed One.
The Gondorians had almost lost Hope. Tolkien makes a play on words, as Aragorn is named Estel in Sindarian, which means Hope.
"I gave hope to men, I leave none for myself".
Onen i-Estel Edain, ú-chebin estel anim
(I gave Hope to the Dúnedain, I have kept no hope for myself.) ~Appendix A, The Return of the King~
The line is from Aragorn's mother, Gilraen; (in the movie RoTK, it is a challenge and reply between Elrond (the first part) and Aragorn (the second)).
Whether spoken by his mother(book), or by Aragorn(movie) this none-too-subtle allusion is to the Messiah in prayer in the garden before the crucifixion. If not allegorical (we'll take Tolkien at his word) the symbolism and applicability is obvious, and fits Tolkien's deeper themes.
Likewise the healing hands of the King, a symbol of the True King noted by Ioreth in Return of the King where he uses kingsfoil to heal.
For it is said in the lore: The hands of the king are the hands of a healer. And so, a rightful king could ever be known. ~(Book V, Houses of Healing)~
In Gondor, the True King is their Hope. Whether any in Gondor outside of Denethor "knew" of an heir, their whole culture hoped for one.
Yet many in Gondor still believed that a king would indeed return in some time to come; and some remembered the ancient line of the North, which it was rumored still lived on in the shadows.
*About that word, Hope.
"Hope" used in this sense is not wishful thinking, but an expectation or belief of something better. That way that "Jesus brings hope to the world" in this sense isn't the same sense as "I hope the Jets win this weekend." This usage was explained to me by a Catholic Deacon when we discussed the nature of belief, and where Hope fits with Faith -- I saw the two as opposed.
Hope, in its widest acceptation, is described as the desire of something together with the expectation of obtaining it.~ The Catholic Encyclopedia, Entry, Hope;
“the ‘sudden joyous “turn”’ of apparently disastrous events, the moment past all hope when we know that everything is going to be all right.” ~ Verlyn Flieger, Splintered Light: Logos and Language in Tolkien’s World (Kent, OH: Kent State University Press, 2002), 27.~
Tolkien on Allegory and Applicability:
“I cordially dislike allegory in all its manifestations, and always have done so since I grew old and wary enough to detect its presence. I much prefer history – true or feigned– with its varied applicability to the thought and experience of readers. I think that many confuse applicability with allegory, but the one resides in the freedom of the
reader, and the other in the purposed domination of the author.” ~J.R.R. Tolkien, The Fellowship of the Ring (Foreward to Second Edition)~