How to advertise a paper to increase citations?
Aside from giving excellent talks at important conferences, here are several other ideas.  I've seen all of these work (although rarely all for the same paper).


Maintain a freely available copy (or at least an arXiv link) on your personal web page.
Keep your CV up to date, including links to freely available version of all your papers.  
Make sure Google Scholar and similar indexing services are indexing your paper.
Announce / brag about your paper on social media: Facebook, Twitter, Google+, LinkedIn, Tumblr, Pinterest, LiveJournal, etc.
If you have pages at clickbait sites like Academia.org or ResearchGate, upload copies (of the arXiv version) there.  (But if you don't, don't start now.)
Write a blog post about your paper.  Better yet, convince someone else with a well-read blog to write a blog post about your paper.
Give invited talks about your work at other universities/labs.  If necessary, invite yourself.
If you are a student, ask your advisor to brag about your new paper.
If your paper significantly extends the work of other authors, or applies it in a novel way, contact those authors directly with a link to (a free version of) your paper.  (But don't send a copy to someone just because you cite them.)
Whenever your paper provides an answer to a question on (for example) physics.stackexchange, answer the question and include a link to your paper.
Develop a reputation for stellar work, so that people in your field regularly check your web page / arXiv / indexes / journals for your newest papers.


The last method is by far the most effective.