As someone who was a professor, my first piece of advice is to establish a relationship with someone you know and respect fairly rapidly. I am still quite good friends with someone who was one my Ph.D. mentors.
Also, should that not be possible, make note of when you had them, what school, year, and, course. The one thing to remember is that, like most people, we tend to remember bad things more than good. You may have to do some prodding.
I myself have never refused generating such a letter from good students. Frankly, I feel honored that someone asked. :)