Não, era basicamente apenas lenda naquele momento. Do apêndice 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'. But these soon became words of ritual little heeded, for the Stewards exercised all the power of the kings. 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 rumoured still lived on in the shadows.

(Return of the King Appendix A: "Annals of the Kings and Rulers")

Gandalf também indica isso em uma conversa com Denethor (ênfase minha):

[T]he rule of Gondor, my lord, is mine and no other man's, unless the king should come again.'

'Unless the king should come again?' said Gandalf.'‘Well, my lord Steward, it is your task to keep some kingdom still against that event, which few now look to see. In that task you shall have all the aid that you are pleased to ask for.

(Return of the King Book V Chapter 1: "Minas Tirith")

No entanto, provavelmente havia apenas três gondorianos que sabiam por certo, e todos aprenderam sobre isso dentro de um ano após Aragorn subir ao trono:

• Boromir, que aprendeu sobre isso no Conselho de Elrond:

  'And who are you, and what have you to do with Minas Tirith?' asked Boromir, looking in wonder at the lean face of the Ranger and his weather-stained cloak.

  'He is Aragorn son of Arathorn,' said Elrond; 'and he is descended through many fathers from Isildur Elendil's son of Minas Ithil.'

  (Lord of the Rings, Book II, Chapter 2, "The Council of Elrond")

• Faramir, que aprendeu com Frodo:

  'If any could claim [the Ring], it would be Aragorn son of Arathorn, whom I named, the leader of our Company from Moria to Rauros.'

  'Why so, and not Boromir, prince of the City that the sons of Elendil founded?'

  'Because Aragorn is descended in direct lineage, father to father, from Isildur Elendil's son himself. And the sword that he bears was Elendil's sword.'

  (Book IV, Chapter 5, "The Window on the West")

• Denethor, que presumivelmente aprendeu sobre isso através do palantír, ou deduziu das menções de Pippin em sua conversa:

  'Do I not know that you commanded this halfling here to keep silence? That you brought him hither to be a spy within my very chamber? And yet in our speech together I have learned the names and purpose of all thy companions. So! With the left hand thou wouldst use me for a little while as a shield against Mordor, and with the right bring up this Ranger of the North to supplant me.'

  (Book V, Chapter 7, "The Pyre of Denethor")

É um pouco mais complexo que "uma lenda" e tem a ver com a esperança

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?

Enquanto a maioria das pessoas em Gondor provavelmente não tinha certeza se algum Dunedain sobreviveu à queda de Arnor, alguns esperado that their True King's line survived. (RoTK, Appendix A, the Fall of Arnor). That the institution of the Mordomo 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 Gray 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 Retorno do Rei 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.

"Esperança" 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;

** eucatastrophe:

“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)~

It was, in your words, "a hopeful legend". When Gandalf and Denethor first meet, Gandalf accuses Denethor (not in so many words) of being duplicitous in speaking for so long to Pippin rather than to him. Denethor replies that such is his right as Steward, and Gandalf reminds him that the office of "Steward" is focused on maintaining Gondor for a coming King:

'If you understand [my purpose], then be content,' returned Denethor. 'Pride would be folly that disdained help and counsel at need; but you deal out such gifts according to your own designs. Yet the Lord of Gondor is not to be made the tool of other men's purposes, however worthy. And to him there is no purpose higher in the world as it now stands than the good of Gondor; and the rule of Gondor, my lord, is mine and no other man's, unless the king should come again.'

'Unless the king should come again?' said Gandalf. 'Well, my lord Steward, it is your task to keep some kingdom still against that event, which few now look to see.'

(Senhor dos Anéis, Book V, Chapter 1, "Minas Tirith"; emphasis added)

Boromir certainly seems to have believed that the King would not come again, according to Faramir. Faramir reports that Boromir was discontented that his father was (and that therefore he would be) "merely" a steward, rather than a king:

'Always it displeased him that his father was not king. "How many hundreds of years needs it to make a steward a king, if the king returns not?" he asked. "Few years, maybe, in other places of less royalty," my father answered. "In Gondor ten thousand years would not suffice."'

(Book IV, Chapter 5, "The Window on the West")

In addition, rhymes mentioning the king and his power (such as the "Come athelas" rhyme recited by the herb-master of the Houses of Healing in Minas Tirith) are now "but a doggrel, ... garbled in the memory of old wives" (Book V, Chapter 8, "The Houses of Healing"), apparently indicating that there's no real expectation of the king being any part of life.

One thing that hasn't been mentioned in the other answers is the reaction of Faramir and Imrahil to Aragorn. Both of them accepted his claim and supported his kingship. Even if the populace was skeptical, it would be hard to mount a challenge against him when current leader and plausible challenger is on the side of the new king. So as it was, anyone who would have been inclined to follow Faramir over Aragorn wound up being in Aragorn's camp anyway.

It was not just 'the hands of the king are the hands of a healer' that helped prove Aragorn was the rightful King of Gondor, or him having the Sword of Elendil, but the slaves on the ships saw Aragorn had control of the Dead. When Angbor alone managed to stand before them Aragorn said

'gather what forces you can for at Pelargir the Heir of Isildur will have need of you'.

Also, when Aragorn arrives at Minas Tirith he comes as a ruler in his own right because he is the ruler of the Dunedain of Arnor, and he has thirty rangers, thirty warriors, to fight under his command. The Rangers represent the king of Arnor's protection of the people of Arnor and Aragorn's kingship. They also represent Aragorn's right to the kingship of Gondor as Elendil's heir.

Finally, Faramir himself supports Aragorn in his claim to the throne of Gondor, as does Prince Imrahil of Dol Amroth, the highest noble of Gondor and Faramir's uncle.