What is the origin of the expression “Yoneda Lemma”? Thank you very much in advance for telling where the expression “Yoneda Lemma” comes from. 
EDIT 1. On page -14 of
Reprints in Theory and Applications of Categories, No. 3, 2003.
Abelian Categories, by Peter J. Freyd
http://www.tac.mta.ca/tac/reprints/articles/3/tr3abs.html
(direct link:  http://www.tac.mta.ca/tac/reprints/articles/3/tr3.pdf )
one reads:

The Yoneda lemma turns out not to be in Yoneda’s paper. When, some time after both printings of the book appeared, this was brought to my (much chagrined) attention, I brought it the attention of the person who had told me that it was the Yoneda lemma. He consulted his notes and discovered that it appeared in a lecture that MacLane gave on Yoneda’s treatment of the higher Ext functors. The name “Yoneda lemma” was not doomed to be replaced.

EDIT 2. In the entry “Grothendieck functor” of the Encyclopaedia of Mathematics [EOM], edited by Michiel Hazewinkel”, one reads

In the English literature, the Grothendieck functor is commonly called the Yoneda embedding or the Yoneda–Grothendieck embedding.

EDIT 3. The article
Grothendieck, Alexander. Technique de descente et théorèmes d'existence en géométrie algébriques. II. Le théorème d'existence en théorie formelle des modules. Séminaire Bourbaki, 5 (1958-1960). Exposé No. 195, 22 p. Février 1960.
quoted in the EOM entry mentioned is available here.
EDIT 4. Subquestion 1: When was the Yoneda Lemma stated in print for the first time? Subquestion 2: When did this Gare du Nord conversation mentioned by Theo Buehler occur? 
The advantage of Subquestion 1 is that it’s more likely to have a definite answer. [I think we all agree on the fact that Grothendieck’s Exposé does contain the “Yoneda Lemma”.]
EDIT 5. Tentative answer to Subquestion 1: I feel (tell me if I’m wrong) there is a consensus on the opinion that the Yoneda Lemma was stated in print for the first time in 
Grothendieck, Alexander. Technique de descente et théorèmes d'existence en géométrie algébriques. II. Le théorème d'existence en théorie formelle des modules. Séminaire Bourbaki, 5 (1958-1960). Exposé No. 195, 22 p. Février 1960. Available here.
[I’m taking this opportunity to thank Theo Buehler for his generous contribution to this thread in particular, and to this site in general.]
 A: 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 (米田信夫).
A: 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.
A: I'm not an expert in the history of the Yoneda lemma, but these days I've been working for a while with Grothendieck's SGA4 (developed around 1963-64, published in 1972), where the "Yoneda" functor and lemma are extensively used.
You can find them stated explicitely too: the "Yoneda" functor in exposé I, construction-définition 1.3 and the "Yoneda" lemma in exposé I, proposition 1.4. Yoneda is not quoted in either cases. Curious, isn't it?
