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 "sailsmenship" salesmenship" are mixed. So while it is always good to have a clear title having an overlly catchy title can also backfire.