It seems clear from the G'mara that the institution of Chanuka as a holiday began the year immediately following the seminal story - with praising of God and commemorating miracles, but there is no mention in that historical retelling of m'nora-lighting as part of the commemorative practice. Are there any records of when this started?
Josephus (Ant. XII:7:7) mentions that "from that time to this we celebrate this festival, and call it Lights." So this association between Chanukah and lights existed already in his times.
In the Gemara, Shabbos 21b, we also find the schools of Hillel and Shammai - who were active from c. 30 BCE to c. 10 CE - debating the proper procedure when lighting more than one candle each night (whether to start with one and work up to eight, or vice versa). So we see from there too that the practice of lighting candles was already in place then, a bit more than a century after the original miracle.
It's quite likely, then, that this enactment was indeed made at the same time that the holiday was established - the year after the miracle.
Have to check other historical records; is it in Maccabees? I don't know. I was taught that the historical records say Chanukah observance was wildly popular at the time (this is suggested as a reason why the Mishna didn't mention it; it was really simple and everyone knew/did it).
The Chanukah narrative in the Talmud is just a quote from Megilat Taanit (the "shared calendar" of the Talmudic era), which was a list of dates and events they commemorated, with regard to either "fast/mourn on this day because it's sad", or "don't fast/mourn on this day because it's happy." So Megilat Taanit just marks Chanukah as "don't fast/mourn; days of praise and thanks." It wasn't the place for discussing its other observances.