Most memorable titles Given the vast number of new papers / preprints that hit the internet everyday, one factor that may help papers stand out for a broader, though possibly more casual, audience is their title. This view was my motivation for asking this question almost 7 years ago (wow!), and it remains equally true today (those who subscribe to arXiv feeds, MO feeds, etc., may agree).

I was wondering if the MO-users would be willing to share their wisdom with me on what makes the title of a paper memorable for them; or perhaps just cite an example of title they find memorable?
This advice would be very helpful in helping me (and perhaps others) in designing better, more informative titles (not only for papers, but also for example, for MO questions).
One title that I find memorable is:


*

*Nineteen dubious ways to compute the exponential of a matrix, by Moler and van Loan.



The response to this question has been quite huge. So, what have I learned from it? A few things at least. Here is my summary of the obvious: Amongst the various "memorable" titles reported, some of the following are true:


*

*A title can be memorable, attractive, or even both (to oversimplify a bit);

*A title becomes truly memorable if the accompanying paper had memorable substance

*A title can be attractive even without having memorable material.

*To reach the broadest audience, attractive titles are good, though mathematicians might sometimes feel irritated by needlessly cute titles

*Titles that are bold, are usually short, have an element of surprise, but do not depart too much from the truth seems to be more attractive in general.
5.101 Mathematical succinctness might appeal to some people---but is perhaps not that memorable for me---so perhaps such titles are attractive, but maybe not memorable.

*If you are a bigshot, you can get away with pretty much any title!

 A: Given the atmosphere of terror and fear in recent years, I did a double take when I first glanced at Bruce Berndt's paper "Ramanujan's association with radicals in India".
A: Finding even sets even faster.
The last fraction of a fractional conjecture.
A: There's an algebra book called "Rings and Ideals".  I thought of a subtitle: "Marriage during the Revolution".
I remember reading Jacobson's "Basic Algebra I" on the bus on the way to university, and someone noticing it and thinking it was a high-school level text.
Similarly, Serre(?) has a difficult book about number theory, titled simply "Arithmetic".
A: John Stallings' "How not to prove the Poincare Conjecture" is lovely.
A: And in the graph theory corner we have the famous Harary/Read paper "Is the null-graph a pointless concept?"
A: Ancestors, Cardinals, and Representatives by T. D. Parsons.
A: I just saw the very curious title:
An Operator-Like Description of Love Affairs
by: Fabio Bagarello and Francesco Oliveri
SIAM J. Appl. Math. Volume 70, Issue 8, pp. 3235-3251 (2010) 
And with the report of this title, I also admit that this title belongs to the category of memorable titles, without first needing to read the paper. The abstract of the paper is also quite curious!
A: I hope it is OK to mention "A Disorienting Look at Euler's Theorem on the Axis of a Rotation" even if I am a joint author, particularly if I admit that none of the authors thought up the cute title---it was the editor. (The cute part is the somewhat subtle use of "disorienting", namely we prove Euler's Theorem for orthogonal transformations that are not proper---i.e., don't preserve orientation.) You can download it here: 
http://mathdl.maa.org/mathDL/?pa=content&sa=viewDocument&nodeId=3542&pf=1
A: A mathematical theory of the guillotine, by Plero Villaggio, Archive for Rational Mechanics and Analysis (1990) Vol. 110, pp 93-101.
A: [Smale, Stephen. The story of the higher-dimensional Poincaré conjecture (what actually happened on the beaches of Rio de Janeiro). A joint AMS-MAA invited address presented in Phoenix, Arizona, January 1989. AMS-MAA Joint Lecture Series. American Mathematical Society, Providence, RI, 1989. 1 videocassette (NTSC; 1/2 inch; VHS) (60 min.); sd., col. MR1057609 (91g:01035)]
It's a video, but it's Smale, so...
A: Andrew Ranicki and the late John Roe were writing
Surgery for Amateurs
A spectacularly funny title, I think.
The incomplete, but very nice, notes can be found online. Thanks again to Nigel Higson for his lovely talk remembering John Roe in the UK Virtual Operator Algebras Seminar.
A: Kevin Buchin, Maike Buchin, Christian Knauer, Günter Rote, Carola Wenk, How Difficult is it to Walk the Dog?, In: Abstracts of the 23rd European Workshop on Computational Geometry, Graz, March 2007, pp. 170-173.
"Walking the dog" refers to finding parametrizations $a : \left[0,1\right]\to C$ and $b : \left[0,1\right]\to D$ of two curves $C$ and $D$ such that $\max_{t\in\left[0,1\right]} \left|\left|a\left(t\right) - b\left(t\right)\right|\right|$ is as small as possible -- or at least smaller than a given cutoff value. The metaphor is a person walking along curve $C$ while keeping a dog on a leash walking along curve $D$. The famous "simultaneous mountain climbers" puzzle has a cameo.
A: The book  $A=B$.  
A: Marginalia to a theorem of Silver (see also this link) by Keith I. Devlin and R. B. Jensen, 1975. A humble title and yet, undoubtedly, one of the most important papers of all time in set theory.
A: I'll echo other comments that the question is wrong-headed, but I think it still serves a purpose.
Comment l'hypothese de Riemann ne fut pas prouvee (How the Riemann hypothesis was not proved), by P Cartier, Seminar on Number Theory, Paris 1980-81, Progr. Math., 22, Boston, MA: Birkhauser Boston, pp. 35-48, MR693308
A: Knobel's wonderful paper on the constant rediscovery of iterated exponentials.

R. Knobel. "Exponentials Reiterated." American Mathematical Monthly 88, (1981), p. 235-252.

A: "A survey of finite differences of opinion on numerical muddling of the incomprehensible defective confusion equation" by B.P. Leonard
A: Larry Bates, Monodromy in the champagne bottle.
A: Larry Bates, "You can't get there from here", Differential Geometry and its Applications 8.3 (1998): 273-274
A: The book of Serge Lang: $\mathrm{SL}_2(\Bbb R)$.
Lang, Serge, $\mathrm{SL}_2(\Bbb R)$, Reading, Mass. etc.: Addison-Wesley Publishing Company. XVI, 428 p. $19.50 (1975). ZBL0311.22001.
A: A Cohomological Viewpoint on Elementary School Arithmetic
A: "On $O_n$" by D.E. Evans.  ($\mathcal{O_n}$ is notation Cuntz gave for the algebras he introduced in "Simple $C^*$-algebras generated by isometries".)
A: Most colorful:
MR1371379 (97g:60105)
Chung, Kai Lai:
Green, Brown, and probability. World Scientific Publishing Co., Inc., River Edge, NJ, 1995. xiv+106 pp. ISBN: 981-02-2453-2; 981-02-2533-4
The book discusses connection between potential theory (in particular Green's function for Laplace equation) and probability (in particular Brownian motions).
A: On manifolds homeomorphic to the 7-sphere
In which Milnor proves there is more than one. 
A: However the question is about papers but it is worth mentioning the title  of Ketonen's PhD thesis: "Everything You Wanted to Know About Ultrafilters But Were Afraid to Ask" !
A: Gaetano Fichera's "Avere una memoria tenace crea gravi problemi" [Having a persistent memory creates serious problems], (Italian), Archive for Rational Mechanics and Analysis 70, 101-112 (1979), MR1553577, Zbl 0425.73002.
The title is a pun to introduce the Author's analysis of time dependent kernels in continuum mechanics: he shows that, while Volterra type kernels (i.e. kernels which are zero before a fixed time $t$ in the past) can be used in the integrodifferential equations of elasticity without affecting existence and uniqueness results involved, the use of general kernels make these results strongly dependent of the topology of the function space on which the problem is posed. The pun is also explained with an analogy at the end of the paper.
A: On the more applied side of things, I'm quite fond of the following (sub)title:
Estimating the number of unseen species: A bird in the hand is worth $\log n$ in the bush
A: A Midsummer Knot's Dream, by Allison Henrich, Noël MacNaughton, Sneha Narayan, Oliver Pechenik, Robert Silversmith, Jennifer Townsend
It is quite funny to read
A: The AKS paper PRIMES is in P is a pretty memorable title for me.
A: Everybody knows what a Hopf algebra is
A: Finding composite order ordinary elliptic curves using the Cocks-Pinch method, by D. Boneh, K. Rubin and A. Silverberg.  (To appear in the Journal of Number Theory.)
A: Zaphod Beeblebrox's Brain and the Fifty-ninth Row of Pascal's Triangle
A: My Ph.D. thesis is titled Why Logical Probabilists Need Real Numbers.  (But I haven't published any paper with that title.)
A: One title I delight in having on my bookshelf is "Introduction to Group Characters" by Walter Ledermann - if you know it's a maths book the title makes complete sense. But a non-mathematician imagines a completely different kind of content.
A: I'm a big fan of "Excluding a Forest": technically precise, to the point, but just mysterious enough to grab the attention. I've said before that it ought to be the name of a band. ("Taming a vortex" is also good.)
A: "K-theory doesn't exist" by Ethan Akin: https://www.sciencedirect.com/science/article/pii/0022404978900324
A: Mathematical physics, for the allusion: "The Unbearable Beingness of Light, Dressing and Undressing Photons in Black Hole Spacetimes" by Timothy J. Hollowood, Graham M. Shore
A: The paper Division by three by Peter G. Doyle and John Horton Conway
A: The missing axiom of matroid theory is lost forever
A emotional variation on absolute negative results.
Refs : Vámos, Peter (1978), "The missing axiom of matroid theory is lost forever", Journal of the London Mathematical Society, II. Ser. 18:
AT : http://jlms.oxfordjournals.org/content/s2-18/3/403.extract
A: I find it dubious that anyone here will get better at choosing titles for their papers by reading these examples. 
Nevertheless, I like the title "The homotopy category is a homotopy category" by Arne Strøm. I also like the very apt title "$\overline{\mathcal{M}}_{22}$ is of general type" by Gavril Farkas. The paper starts like this: 
The aim of this paper is to prove the following result:
Theorem: The moduli space of curves of genus 22 is of general type.
A: A Group of Order 8,315,553,613,086,720,000 by J H Conway, Bull. London Math. Soc. (1969) 1 (1): 79-88, https://doi.org/10.1112/blms/1.1.79
Maybe it's cheating to call this memorable - I remembered there was a Conway paper with a title of this type, but I certainly don't claim to have remembered the exact title!
A: An application of Poincaré's recurrence theorem to academic administration by Kenneth Meyer is a title that is hard to resist looking into.
A: I always remember the paper entitled "On groups of order one."  It turned out the title referred to groups defined by generators and relations, so the problem was to determine when a set of elements (together with its conjugates) generated a free group.  I cannot imagine any mathematician who would not look at this paper to see what it was about.
A: I really like humor in scientific texts, specially in titles. One of my favorite authors is Donald E. Knuth. A title like The sandwich theorem makes me curious about its content. The Art of Computer Programming is also a nice title.
A: Mathematical Fallacies, Flaws and Flimflam was definitely by far the most memorable title I have ever read. Also A Taste of Topology seemed tasty.
But I would also like to stress, that to me, the books that have the most 'classical' and 'general' titles, seem the most appealing. Eg.

*

*Graph Theory,

*Algebraic Topology,

*Algebraic Geometry,

*Abstract Algebra,

etc.
A: I like the second part of:
Breuil, Christophe; Conrad, Brian; Diamond, Fred; Taylor, Richard "On the modularity of elliptic curves over $\mathbf{Q}$: wild 3-adic exercises."
MR1839918 (2002d:11058)
They prove the remaining cases of the Shimura-Taniyama conjecture: "every elliptic curve is modular".
A: "A short tale of hybrid mice", by Grigor Sargsyan.
A: The Chekanov torus in $S^2\times S^2$ is not real. Quite a philosophical title and I could never forget about it...
A: My personal favorite is Elisabetta A. Matsumoto's:
"The Taming of the Screw: or How I Learned to Stop Worrying and Love Elliptic Functions"
which can be found here. It is a very good read, and the title extremely seamlessly references both Shakespeare and Dr.Strangelove; two of my favorites.
A: Honey, I Shrunk the Sample Covariance Matrix
A: The book Free rings and their relations by P.M. Cohn.
A: Very late addition (August '13) J. J. Sylvester, Thoughts on inverse orthogonal matrices, simultaneous sign-successions and tesselated pavements in two or more colors, with applications to Newton rule, Ornamental tile-work, and the theory of numbers. Phil Mag 34 (1867), 461-475.
This title is unbeatable!
Late addition (March, '13): Long and Wigderson's "  How discreet is the discrete log?."
Gale and Shapley's "College Admissions and the Stability of Marriage, " was a great title to a great paper. (link JSTOR)
"Moments in mathematics" Papers from the American Mathematical Society annual meeting held in San Antonio, Tex., January 20–22, 1987. Edited by Henry J. Landau. (Link: Google book)
This is about "moments" in the technical sense but the double meaning of the title is very cute. (There is also a book entitled "great moments in mathematics" with the ordinary meaning of moments.)
About 1-2 decades ago Sylvain Cappell and Shmuel Weinberger planned writing a book called "A piece of the action" about group actions. This is a memorable title but I think the book was not completed.
One obvious: Aigner and Ziegler's Proofs from the book. (Link: WikipediA)
Joel Spencer's title "Six standard deviations suffice." is also memorable. (Link: JSTOR)
Jack Edmonds',(1965) "Paths, Trees and Flowers". (Link: ps file.)
For some reasons I found the title "Defect Sauer results" of a paper by Bollobas and Radcliffe memorable. (Link)
Branko Grunbaum has a paper entiled "The importance of being straight" (I could not find a link), and Irit Dinur and Shmuel Safra have a paper entitled "On the importance of being biased". (A link to a later version with a different title.)
(There is a paper by A. Dillof published in Michigan Law Review with very similar name.)
Jorg Wills had a memorable title "decomposable skeleta" for a paper he sent for the 100th birthday of a well known mathematician. But I think at the end he changed the title.
Saharon Shelah has several memorable titles like this one: "On what I do not understand (and have something to say). I" .Although, I forgot the most memorable one.
A: Here is a list of papers in Theoretical Computer Science with cute titles. Some that I like from the list (aside from "Mick gets some" which is good enough to deserve its own answer anyway).

*

*A Smaller Sleeping Bag for a Baby Snake

*The Art of Pointless Thinking: a Student's Guide to the Category of Locales

*Scott is not always sober

Also: Mangoes and Blueberries.
And in a similar vein, a quote from "Quotients homophone des groupes libres - Homophonic quotients of free groups," that appears on the first linked page page: "Ah, la recherche! Du temps perdu."
A: "I know I should have taken that left turn at Albuquerque" by Gady Kozma and Ariel Yadin (https://arxiv.org/abs/1008.4258)
A: "Holey Sheets" - Pfaffians and Subdeterminants as D-brane Operators in Large N Gauge Theories.
A: There are not exactly five objects
by Andreas Blass
A: Integrity of ghosts, by Gert Almkvist.
Gert Almkvist's generalization of a mistake by Bourbaki, by Doron Zeilberger. (And a few more by the same author.)
The Point of Pointless Topology, by Peter Johnstone.
The absolute classic: Go To Statement Considered Harmful, by Edsger Dijkstra.
A: Quantum lower bounds by quantum arguments.
A: Some nice titles from B.A. Kupersmidt:


*

*KP or mKP (a book)

*Dark equations (an article)

A: Using the Logistic Map to Generate Scratching Sounds
The first sentence in the abstract:

This article presents a mathematical model for generating annoying
scratching sounds.

A: Smullyan: what is the name of this book?
Mazzola: The Topos of Music
A: « Autopsie d'un meurtre » dans l'homologie d'une algèbre de chaînes ("Anatomy of a murder" in the homology of a chain algebra)
by J.-M. Lemaire,
http://www.numdam.org/item/ASENS_1978_4_11_1_93_0/
(For those who do not care about old movies as much as I do, the title of course alludes to the iconic film of Otto Preminger https://en.wikipedia.org/wiki/Anatomy_of_a_Murder)
A: Atiyah's K-Theory and Reality
A: H=W
It's a paper showing that two methods of defining Sobolev spaces, one which uses H's with subscripts and superscripts and one that uses W's, give rise to the same spaces.  
Thanks to Willie Wong for the following:
Citation information
@ARTICLE{MeySer1964,
  author = {Meyers, Norman G. and Serrin, James},
  title = {{H = W}},
  journal = {Proc. Natl. Acad. Sci. USA},
  year = {1964},
  volume = {51},
  pages = {1055-1056},
  number = {6},
  file = {MeySer1964.pdf:MeySer1964.pdf:PDF},
  owner = {ww278},
  timestamp = {2010.05.03},
  url = {http://www.pnas.org/content/51/6/1055.short}
}

A: I'm quite surprised that no one has mentioned The Joy of Sets by Keith Devlin.
A: J.-M. FONTAINE
Il n'y a pas de variété abélienne sur Z
Invent. Math. (1985) 81, 515-538
A: Homotopy Algebras are Homotopy Algebras  by Martin Markl
A: You'd think that with John H. Conway around, this should be like shooting fish in a barrel. One title that comes to mind is

*

*The Sensual (Quadratic) Form

and there are more goodies if you look at his bibliography. For example,

*

*Character Calisthenics

or

*

*The $\sqrt{\text{Monster}}$ Construction

I also like the paper (both the title and the contents!) by Andreas Blass,

*

*Seven Trees in One
A: I can't believe no one's mentioned this:

*

*Pavol Ševera, Some title containing the words "homotopy" and "symplectic", e.g. this one, arXiv:math/0105080
A: OK, fine... I'll confess I could not resist downloading from the arxiv the paper Act globally, compute locally: group actions, fixed points, and localization. I don't know if it quite fits the question though, since I never read it (beyond the first couple of pages). It's just way too far outside of my main interests.
A: Todd's "The 'odd' number six."
A: I've always enjoyed the poetry of the title:
"Period three implies chaos"  -- T.-Y. Li & J. A. Yorke
A: Addictive Number Theory, by Melvyn B. Nathanson.
A: "Fun with $\mathbb{F}_{1}$"
https://arxiv.org/abs/0806.2401
Quite a decent pun, I think.
A: At some point in time the Erdős collaboration graph did not contain an (induced) $K_5$, but it did contain a $K_5$ with one edge missing. Someone showed me a paper with a title something like "The Erdős graph contains a $K_5$," written by the two authors that formed the missing edge. The rest of the paper was blank, since the names of the authors were sufficient to prove the statement of the title. Not really a memorable title per se, but it becomes quite memorable when the authors are included.  I couldn't find any mention of this paper on the web, however.
A: Mickley, Smith and Korchak's Fluid flow in packed beds.
(No-one in fluid mechanics seems to be willing to see the innuendo. They
all want to explain the effect on the Reynolds number. And they hate it
if you snigger when they mention turbulence.)
A: Old and new on SL(2) by Hilgert and Hofmann. I heard that the authors wrote a sequel with the title More is true on SL(2), but that the editors insisted on a different title.
A: "49598666989151226098104244512918" by Michael Filaseta and Samuel Gross
A: "Footnote To a Note of Davenport and Heilbronn" by J. W. S. Cassels.
https://jlms.oxfordjournals.org/content/s1-36/1/177.extract
A: *

*Andrew Stacey and Sarah Whitehouse, The hunting of the Hopf ring,
Homology, Homotopy and Applications, Vol. 11 (2009), No. 2, pp.75-132. doi:10.4310/HHA.2009.v11.n2.a6, arXiv:0711.3722
referencing this poem. Much more memorable than the related works by the same authors:

*

*Andrew Stacey and Sarah Whitehouse, Tall-Wraith monoids, arXiv:1102.3549


*Andrew Stacey and Sarah Whitehouse, Stable and unstable operations in mod $p$ cohomology theories, Algebr. Geom. Topol. 8(2) (2008), 1059–1091, doi:10.2140/agt.2008.8.1059, arXiv:math/0605471
A: The book Why Knot? by Colin Adams.
A: Approximately counting up to four, by Luby and Vigoda.
A: Lovasz's "Hit and Run Is Fast and Fun". In that he proved the hit run algorithm on sampling from log concave distributions on a convex set in the Euclidean space has a polynomial mixing time, hence fast. 
A: My memory is marked by the titles of two papers by Branko Grünbaum:

*

*Branko Grünbaum. `Are your polyhedra the same as my polyhedra?' Discrete and comput. Geom.: the Goodman-Pollack Festschrift, ed. B. Aronov et al, Springer (2003), pp. 461-488.


*Branko Grünbaum. `The Bilinski Dodecahedron and Assorted Parallelohedra, Zonohedra, Monohedra, Isozonohedra, and Otherhedra'. The Mathematical Intelligencer (2010). DOI: 10.1007/s00283-010-9138-7.
The first title is easy for me to recall whenever I need to refer to the paper. The second title sounds fancy (though the article itself is not) and, more importantly, is unpronounceable by me, therefore I have put some stretch of mental effort into memorising it.
As to the original question---What makes the title of a paper memorable?---, personally, when I look for things to read, my attention tends to be captured by titles that are short and sweet, for instance, Jean-Pierre Serre's Trees, Ken Brown's Buildings. These monographs/papers usually turn out to be the authoritative treaties of the topics, with material unforgettable for one working in the field.
A: "The 40 billionth binary digit of pi is 1", D. Bailey and P. Borwein.
A: I don't think $\textbf{L'endoscopie tordue n'est pas si tordue}$ (Twisted endoscopy is not so twisted) de J.-L. Waldspurger has been mentioned yet. 
A: Paul Halmos' Applied Mathematics is Bad Mathematics is certainly a memorable title, notwithstanding the wrong-headedness of what at least superficially appears to be its thesis.
A: One of my favorite titles from control theory is a 1978 paper by John Doyle entitled "Guaranteed Margins for LQG Regulators." It is memorable because of the abstract "There are none." The paper shows that optimal controls may be fragile; the 3-word abstract says it all.
A: The flattering lie  You Could Have Invented Spectral Sequences  by Timothy Y. Chow. 
A: "Hodge's general conjecture is false for trivial reasons."
A: Ideals and reality
projective modules and number of generators of ideals
By Friedrich Ischebeck and Ravi A. Rao
A: Street-Fighting Mathematics by Sanjoy Mahajan is about estimation, Fermi calculations, dimensional analysis and so on.
I haven't read it yet, but the title was certainly enough to get me to download it.
A: From the top of my head comes the papers

*

*Domination When The Stars Are Out, D Hermelin, M Mnich, EJ van Leeuwen, G Woeginger

*Looking At The Stars, E Prieto & C Sloper

*Leftovers from the Ham Sandwich Theorem, G Byrnes, G Cairns and B Jessup

But also, Cox & Zucker, who in Intersection numbers of sections of elliptic surfaces creates the algorithm later named the Cox-Zucker machine
A: One that comes immediately to mind is Can one hear the shape of a drum?
A: On the Dreaded Right Bousfield Localization by C. Barwick.
A: Noone beats Mick gets some (the odds are on his side) by V. Chvatal and B. Reed. It is an article about the satisfiability problem, and the title is of course referring to this song. I havn't read the article, and the only reason I know the it is its title.
A: Ben Andrews' : "Gauss curvature flow: the fate of the rolling stones"
A: There was the fuss about The Yellow Cake, a joint paper of Saharon Shelah and Andrzej Roslanowski. (Wayback Machine)
They also co-authored several other funnily titled papers, amongst them are such names as:

*

*"How much sweetness is there in the universe?"

*"Measured Creatures"

*"Lords of the iteration"

*"Sweet & Sour and other flavours of ccc forcing notions"

A: A minus sign that used to annoy me but now I know why it is there by Peter Tingley.
A: Fractured Fractals And Broken Dreams. Self-similar Geometry through Metric and Measure. Guy David, Stephen Semmes.
http://www.oup.com.au/titles/academic/maths/9780198501664
This is the most unusual title of a book which I have ever come across. I discovered this  while randomly browsing through books in the library and got hooked. I was an undergraduate then and it had a strange attraction to me, even though I could not figure out anything that was written in it then.
I was not the only one! 
Our university used to put out a list of courses (in the good old days) which were going to be offered and students would choose from it. Some of us managed to add the name of this book against the fractal geometry course as a course material. A record number of students enlisted. 
Within a week a record number of them wanted to opt out. So there were inquiries: it turned out most of the students cited that they found the title of the  book mentioned in the course material attractive which prompted them to enlist.   
(We had found in the previous year that the instructor did not care about teaching, insist on taking class at 8 in the morning and would religiously take attendance for 10 minutes, by the end of the class half the class would be snoring. The assignments were to be submitted on A4 paper, we were supposed to write on one side with appropriate margin.
It was a case of a pun / warning which had gone horribly wrong. )     
A: There are some rather obvious aspects to the question that perhaps should be mentioned.
"For a large number of readers, the choice whether they select to read a paper or not is often strongly influenced by the title."
Yes, but it is also strongly influenced by the abstract and introduction.
"I was wondering if the MO-users would be willing to share their wisdom with me on what makes the title of a paper memorable for them; or perhaps just cite an example of title they find memorable?"
Since most answers refereed to the second part, perhaps it is worth answering the first part of the question as well. Perhaps the main thing that makes the title (and paper) memorable is the content of the paper.
"This advice would be very helpful in helping me (and perhaps others) in designing better, more informative titles (not only for papers, but also for example, for MO questions)."
Overall, the reaction in the mathematics community to catchy titles, personal descriptions, jokes of various kind, and various other things that can be seen as PR-related or "salesmanship" are mixed. So while it is always good to have a clear title having an overly catchy title can also backfire.
A: How to Gamble If You Must by Lester E. Dubins & Leonard J. Savage
A: “Kindergarten Quantum Mechanics” by Bob Coecke / arXiv:quant-ph/0510032v1
A: How often should you beat your kids?, by Don Zagier. The conclusion is that you should beat your kids every day except Sunday!
The word "beat" in this context means to defeat your child in a certain card guessing game, which the paper shows that you will win with asymptotic probability $\frac12+\frac1{2\sqrt{2}}\approx\frac{6}7$, hence six days out of seven.
Despite the intentionally shocking title, the paper is quite a good read!
A: Mark Van Raamsdonk's Princeton PhD thesis in string theory was called "Making the most out of zero branes and a weak background". Priceless.
http://adsabs.harvard.edu/abs/2000PhDT........40V
A: Al Capone and the Death Ray by R. C. Lyness
A: Simmons, F. W., When Homogeneous Continua Are Hausdorff
Circles (or Yes, We Hausdorff Bananas), Continua, Decompositions, and Manifolds,
University of Texas Press (1980) pp. 62-73.  I think it's a reference to this song.
A: I always like the title "Homology flows, cohomology cuts" by Chambers, Erickson and Nayyeri, which makes analog (a general technique indeed) to the well-known theorem (for graph theorists) "Maximum flows, minimum cuts".
A: A Tale of Two Sieves by Carl Pomerance
A: I like Cliff Taubes's simple titles: "Gr -> SW", "SW -> Gr", and "SW = Gr". (Okay, they each also have a subtitle, but the first part is enough to tell the reader exactly what the paper is about.)
A: Theorems for free! by Philip Wadler
From the abstract: ... This provides a free source of useful theorems, courtesy of Reynolds' abstraction theorem for the polymorphic lambda calculus. 
A: "What is infinity factorial (and why might we care)?"
The only downside is that it isn't actually typed up, but rather is hand-written and scanned, but the result of $\infty! = \sqrt{2\pi}$ is still rather intriguing.
A: De Weger and Pinter wrote this paper entitled:
$$210 = 14 \times 15 = 5 \times 6 \times 7 = \binom{21}{2} = \binom{10}{4}$$
A: The weird and wonderful chemistry of audioactive decay, by John Conway.
A: Here are a few that jump to my mind.
Young person's guide to canonical singularities by Miles Reid, 1985.
Twenty-five years of 3-folds—an old person's view by Miles Reid, 2000.
Tendencious survey of 3-folds, by Miles Reid, 1985 (same book, Bowdoin -- Algebraic Geometry, as the first one).
On the ubiquity of Gorenstein rings by Hyman Bass, 1963.  This also seems to be the first paper with the word ubiquity in the title (via a mathscinet search).
Another one that jumps to my mind is the various Pathologies papers of Mumford.  
A: Speaking of Milnor and such things, have we already done [Edit: Kervaire-Milnor's] "Groups of Homotopy Spheres"?
A: You can find in Serre's Œuvres (volume IV) an article titled $\Delta = b^2 - 4ac$. (Wayback Machine)
A: Crocheting Adventures with Hyperbolic Planes by Dr Daina Taimina (A K Peters), see
http://www.thebookseller.com/news/114989-crocheting-adventures-wins-diagram-2009.html (Wayback Machine)
https://en.wikipedia.org/wiki/Bookseller/Diagram_Prize_for_Oddest_Title_of_the_Year
http://hyperbolic-crochet.blogspot.com/
A: Great Expectations: The Theory of Optimal Stopping,
Yuan Shih Chow, Herbert Ellis Robbins, David Siegmund
Houghton Mifflin, 1971
A: Bob Thomason's "Beware the Phony Multiplication on Quillen's $A^{-1}A$".
A: Not math, but Alpher, Bethe, and Gamow is hard to beat
A: Another one:
MR1274760 (95d:30040)
Carleson, Lennart(S-RIT); Jones, Peter W.(1-YALE); Yoccoz, Jean-Christophe(F-PARIS11)
Julia and John. (English summary)
Bol. Soc. Brasil. Mat. (N.S.) 25 (1994), no. 1, 1–30.
The preprint wad even more memorable title:
In Carleson and Gamelin's book on complex dynamics it was referred to as: When is Julia John?
A: My favourite :  "My Graph", by H.S.M. Coxeter.
A: The following is not quite as arresting as the other titles listed, but Stallings has a paper in Inventiones entitled "The topology of finite graphs".  It's a pretty gutsy title, but what's even more impressive is that it is a fairly good description of what the paper contains (namely, a totally new approach to studying questions about subgroups of free groups using finite graphs; this is totally different from the classical approach using covering spaces of graphs)!
A: I have always found the book title "Prolegomena to a Middlebrow Arithmetic of Curves of Genus 2" by Cassels and Flynn to be quite memorable.
A: The Chemical Basis of Morphogenesis. Alan Turing.
A math paper use chemical principles explaining biological phenomenon. 
A: Would a book titled Calculus Made Honest get me burned at the stake for heresy?  
Or would it merely confuse mathematicians who don't understand what is in need of being made honest in that topic?
Later edit: This question illustrates nicely the emotional nature of the anonymous voting system.  Robin Chapman commented: "So, it isn't an actual title, and so this reply is not an answer to the original question."  
That proves that he never read the original question and didn't know what it said.  Probably he drew an inference about its content from the many answers.  Then people rushed in with "down" votes.  I invite anyone who has doubts about this to read the original question by Suvrit, and I invite Robin Chapman to read it for the first time.
[Original answer by Michael Hardy.]
