Thorongil

[HerenIstarion]

Aragorn was disguised. Yes, as simple as that.

Tale of Years

2957-80 Aragorn undertakes his great journeys and errantries. As Thorongil he serves in disguise both Thengel of Rohan and Ecthelion II of Gondor.

and, though Theoden did not recognize him, that is not because he haven't seen him before:

LoTR, Book III, Chapter II

'I do not think your law was made for such a chance,' said Aragorn. 'Nor indeed am I a stranger; for I have been in this land before, more than once, and ridden with the host of the Rohirrim, though under other name and in other guise. You I have not seen before, for you are young, but I have spoken with Éomund your father, and with Théoden son of Thengel.