What exactly did Hashem order Moshe to record?
Rashi: That Amalek was the first of all the nations to attack Yisrael.
Ramban and Seforno: To insert in the Torah Parshas Zachor (in Ki Seitzei). 1
Targum Yonasan: He ordered Moshe to record the battle with Amalek in the Book of Chronicles, in which the battles that were fought were recorded. 2
And what did Hashem instruct him to pass on into the ears of Yehoshua?
Rashi: He told him to instruct Yehoshua to command Yisrael to pay Amalek his dessert for being the first to attack Yisrael.
Rashbam: That he should fulfill the Mitzvah of destroying Amalek.
Vilna Gaon: He taught Yehoshua that the word "Zeicher" should be read accordingly. 3
Why specifically Yehoshua?
Rashi: Because Yehoshua was destined to lead Yisrael into Eretz Cana'an. 1
A hint that it would be Yehoshua, and not he, who would be granted that privilege (Rashi).
And what did Hashem mean when He said that He would destroy the memory of Amalek?
Seforno: He meant that He would destroy even his animals. 1
What are the implications of "Machoh Emcheh ... "?
Rashbam: Because it is Hashem's will that Amalek's name be erased.
Rosh: Hashem Himself will erase Amalek's name after he (Amalek) stretched out his hand to destroy the Beis-ha'Mikdash. 1
Prior to that, it is incumbent upon us to do so - as the Torah states at the end of Ki Seitzei.
What is the meaning of "mi'Tachas ha'Shamayim"?
Sifri: That nothing will remain of Amalek - no child or offspring, no camel or donkey; so that nobody will be able to (point a finger and) say 'This belongs to Amalek'.