So, how to get a good recommendation. Just ask your professors, would you give me a recommendation, and would you expect me to get in. If they are actually going to give you a good recommendation, they will tell you that they definitely expect you to get in. If they are sort of noncommittal, you are probably going to get a mediocre recommendation. Ask them what you would need to do to be a great candidate. Then do that.
Publication helps of course, especially in convincing your professors to give you a good rec. If you don't have any publications or ideas on how to get some, you might try a REU.
Win the Putnam. :-)
Of course, in order to be in a position to pick a good supervisor, you need to make yourself attractive. Do research; publish papers; go to conferences and present your work there; talk to other people in your field. Faculty are always looking for more good graduate students, and meeting them at conferences will give you a chance to figure out if you get on well with them at a personal level.
That said, I did almost none of the above -- but I was a special case, in that I didn't particularly need any supervision (I'm pretty certain that I literally saw my supervisor less than two dozen times while I was a graduate student, and interacted far fewer times than that).