The earliest source, I believe, is the Abudrahem, a student of the Baal Haturim (son of the Rosh) who lived in 14th century spain (see inside the Sefer here)
ובמקצת מקומות אומרין אותו כל יום מפני
שנקרא מזמור המנורה והקורא אותו בכל יום נחשב
כמדליק המנורה הטהורה בבית המקדש וכאלו מקבל
פני שכינה כי תמצא בו ז׳ פסוקים כנגד שבעה קני
המנורה
The Abudrahem goes on to explain that this Psalm has 49 words which relate to the 49 different parts of the Menorah - thus why we always recite this Psalm after counting the 49 days of the Omer.In some places (the Lamnatzeach) is recited every day since (this psalm) is called the Psalm of the Menorah and when you recite it everyday, it is considered as you lit the Menorah in the Beit Hamikdash (...)
Another possible early source for this claim is the Ramban, who reportedly brings this same commentary in one of his letters adding that it should be recited specifically at sunrise, but this letter is not to be found presently.
Rabbi Yitzhak Haezovi (Turkey, 15th Century), in his sefer Agudat Ezov, confirms that there's a tradition that "whoever recites this Psalm throughout the 49 days of Omer nothing bad will happen to him that year". Perhaps you shouldn't take this lightly because he adds that King David took this very seriously:
The Agudat Ezov goes on to say that it's good to have it embroidered in the Aron of the synagogue to protect the community - which explains why you always see this Menora Lamnatzeach in the Sephardic shuls today."This Psalm was engraved in gold in King David's shield, made like the shape of the Menorah and when he went to wars he would meditate upon it (...) and with it he would win his enemies"
Another early Kabbalist that mentions this is the Akeidat Yitzhak, who was one the last Rishonim who lived in the Golden Years of Spain's Jewry in the 15th century, and he pretty much mirrors what the Agudat Ezov said - see here in full.
The Chida, one of the greatest Kabbalists of the 18th century, adds that it should be recited from Klaf - parchement (direct source here).
I must also highlight this fascinating piece from the Ben Ish Chai, arguably the most respected Kabbalist of the 19th Century and a household name in every Sephardic home, who says that you don't need specifically klaf - any paper is fine according to him - but he adds a powerful twist:
יזקוף את הציור של המנורה שמסתכל בו כדי שיהיה הציור זקוף לפניו כדמיון המנורה שהיתה זקופה ועומדת בהיכל ולא יניח הציור מושכב ושטוח לפניו כשאומר למנצח בנגינות מזמור שיר המצוייר בצורת המנורה על קלף או על נייר,
Fascinating comment. I bring it because it illustrates how dear this Psalm is to all Kabbalists, early and contemporary, to such an extent that they even instituted it in the everyday prayers of the 49 days of the Omer, something that today is standard practice in virtually all Jewish communities. From there, as the Abudrahem mentioned above, some people started to say this Psalm every day and, as we see today in our Siddurim, it is recited just before Baruch Sheamar in Shacharit (nusach sephard and edut mizrach). That placement is puzzling because the Ari, who basically reorganized what is today Nusach Sefrad and Edut Mizrach, actually said that we should mention it at the end of Amida, right before Elokai Netzor:
ולכן יהיה תמיד נגד עיניך גם תאמר בכל יום אחר תפלת ערבית ומנחה ושחרית אחר העמידה קודם אלקי (full text here, difficult read) נצור מזמור ס"ז והוא מזמור למנצח בנגינות מזמור שיר
I've seen that Rabbi Pinchas Zbihi brings why we recite it before Baruch Sheamar; something to do with the daily ritual of the lighting of the Menora but that's beyond the scope of this already complicated post.
Interestingly, Rabbi Zbihi elsewhere says that the Abudrahem - who said that reciting Menora Lamnatzeach is like lighting the Menora - might explain why we say it every weekday mornings but not on Shabbat. If it is like lighting the Menora that is a forbidden Melacha (!) and that might explain why our Siddurim have another Psalm in its place.
The big question is why the vast majority of Siddurim don't print this Menora layout both before Baruch Sheamar and also by Sefirat Haomer. As we have seen, the point is not only to recite this Psalm but to recite it in this specific shape and we rarely see this in contemporary siddurim.
But to finalize this post, I must mention a very practical consideration. There is a very famous discussion concerning the exact look of the Beit Hamikdash's Menora and this has implications for the Lamnatzeach Menora. The Maase Choshev says that the Menora was curved, as seen in the infamous Arch of Titus and many archeological findings. It happens to be the the vast majority of Menorah Lamnatzeach follow this layout, as seen below:
There's one major problem with this layout - it's very difficult to make round "Sirtut" (guiding lines) and as the Talmud in Sanhedrin notes, it's forbidden to write more than four words in parchement without guiding lines. Aside this technical problem, Rashi and Maimonides held that the Menora was not curved but straight - the late Lubavitch Rebbe actively advocated (see Likkutei Sichot vol. 21) to spread this layout and that's by the way why all Chabad's public Menoras in Chanukka are always straight. For these reasons, there's an alternative Lamnatzeach:
I however never saw this layout in any synagogue; it's not very popular. But a third layout, which is squared and doesn't conform with any of the two opinions mentioned above, is extremely popular and present in many Chassidic synagogues. It is also printed in my Ktav Ashurit Siddur:
I speculate that because of the Sirtut problem in the rounded layout, Sofrim started to write the round Lamnatzeach in this way which resembles the rounded scheme and at the same time has regular straight guiding lines (Sirtut).
Last week I received a long awaited shipment of red Gvil parchement and it was just big enough to write a Lamnatzeach Menora. I used the square layout because I think it's the nicest and also because it's the middle way between the rounded and the straight Menora. I will record my experience with this Gvil in another post.