What is the origin of the expression “Yoneda Lemma”?
Disclaimer: I'm posting this answer to back up Zhen Lin's answer to the end that Mac Lane is responsible for that terminology. Unfortunately, I can't find a first hand quote by Mac Lane online, but when I asked myself the same question several years ago, I tracked down many sources, but I can't find my notes on that at the moment, so I'm quoting from my unreliable memory and all has to be taken with a grain of salt. However, it is definitely worth getting copies of the references I provide below that aren't available online.
Edit 3: In a nutshell my answer boils down to the following: Organize a copy of issue 47 (1) (1998) of Mathematica Japonica and read the articles by Mac Lane (page 156) and Kinoshita (page 155). Snippet views of that issue are available on Google Books.
Here's a somewhat more extensive quote from the "Notes" on pages 77f of Mac Lane's Categories for the Working Mathematician:
The Yoneda Lemma made an early appearance in the work of the Japanese pioneer N. Yoneda (private communication to Mac Lane) [1954]; with time, its importance has grown.
Representable functors probably first appeared in topology in the form of "universal examples", such as the universal examples of cohomology operations (for instance, in J. P. Serre's 1953 calculations of the cohomology, modulo 2, of Eilenberg- Mac Lane spaces).
I think that in the first paragraph there is simply a comma missing between the parentheses and the square brackets referring to the 1954 article by N. Yoneda, On the homology theory of modules, J. Fac. Sci. Tokyo, Sec. I. 7, 193–227 (1954). MathSciNet review by H. Cartan: MR 68832 (in French). Edit: Of course, this could also be interpreted to mean that the meeting between Mac Lane and Yoneda at the Gare du Nord (see below) took place in 1954.
If I remember correctly, Yoneda doesn't prove his lemma in that article (see also the quote by Freyd in Edit 1 of the question). However, he proves that the left derived functors of a (right exact) functor $F: {}_R\mathbf{Mod} \to \mathbf{Ab}$ can be computed as $L_{q}F(A) = [\operatorname{Ext}_{R}^{q}((A,{-}),F]$ where the right hand side denotes the abelian group of natural transformations from the $q$th Yoneda Ext to $F$. In the course of the proof he essentially establishes the Yoneda Lemma for $R$-modules (which is the case $q = 0$ of course). See also Yoneda's follow-up paper On $\operatorname{Ext}$ and exact sequences, J. Fac. Sci. Univ. Tokyo Sect. I 8 (1960) 507–576. MathScinet review by G. S. Rinehart: MR 226854.
Edit 4: It may be off-topic but I think it's still worth pointing out, as it isn't as well-known as it deserves to be: Yoneda's second paper introduces what is nowadays called an exact category in the sense of Quillen, under the name of quasi-abelian $\mathscr{S}$-category. See the historical note on p.3f of my survey article for more on that (preliminary version available as arXiv:0811.1480 where the note is on p.4). Note that Yoneda's paper precedes Quillen's seminal Higher algebraic $K$-theory, I, Springer LNM 341 (1973), 85-147 by 13 years. MathSciNet review of Quillen's paper by S. M. Gersten: MR 338129.
Furthermore, there is the story that Yoneda and Mac Lane met in Paris at the Gare du Nord, where Mac Lane learned about it:
When he [Yoneda] arrived in Princeton, Eilenberg had moved (sabbatical?) to France (or maybe, Eilenberg left US just after Yoneda's arrival). So, Yoneda went to France a year later. At that time, Saunders Mac Lane was visiting category theorists, apparently to obtain information to write his book (or former survey), and he met the young Yoneda, among others. The interview started in a Café at Gare du Nord, and went on and on, and was continued even in Yoneda's train until its departure. The contents of this talk was later named by Mac Lane as Yoneda lemma. So, the famous Yoneda lemma was born in Gare du Nord. This must have been a good memory for Yoneda; I heard him tell this story many times. I do not know whether Mac Lane managed to leave the train before departure!
Edit 2: This excerpt is from an email by Yoshiki Kinoshita on occasion of Yoneda's death. From what I could see on Google Books the above paragraph appeared in polished form on page 155 in issue 47 (1) (1998) of Mathematica Japonica. See also Kinoshita's article A bicategorical analysis of $E$-categories, Mathematica Japonica, 47(1), 157-169, 1998.
See also the first paragraph on p.3 of C. McLarty's article Saunders Mac Lane and the Universal in Mathematics, Scientiae mathematicae Japonicae 19 (2006) 25–28:
Rather than recount the often told collaboration with Eilenberg, let us focus on the most famous lemma in category theory. Many aspects of Mac Lane’s thought are captured in the history and the mathematics of this result. Mac Lane was passionate about organizing and building the knowledge of category theory. He knew Nobuo Yoneda’s work in homology and so when they met in Paris Mac Lane eagerly talked with him about his wider, unpublished perspective on the methods. Mac Lane’s care as a historian of mathematics shows in his account of learning this lemma from Yoneda on a platform of the Gare du Nord waiting for Yoneda’s train (Mac Lane 1998b).
Reference 1998b in McLarty is: Mac Lane, The Yoneda lemma, Mathematica Japonica 47, 156, which unfortunately I could not locate online.
Finally, there is a passage in Mac Lane's autobiography telling the story on the Gare du Nord and I distinctly remember that Buchsbaum said that he learned about the Yoneda Lemma from Mac Lane in lectures on category theory.
According to Mac Lane [CWM, 1998, p.77]:
The Yoneda Lemma made an early appearance in the work of the Japanese pioneer N. Yoneda (private communication to Mac Lane) [1954]; with time, its importance has grown.
N. Yoneda refers to Nobuo Yoneda (米田信夫).