I've had to do this for award applications in the past. To add to the other answers:
With respect to *when*, you first and foremost want to ensure that you give recommenders ample time to actually write their references / letters. Professors are busy people and they will view the situation unfavourably if the deadline is approaching.
Moreover, you'll want to choose a professor with whom you have some history. The easiest route is to select a professor of a class that you did well in. However, even these recommendations will be relatively weak if the only thing they can say about you is that you got a good mark in their class. The best case is where a professor is more familiar with your work and character. This could come from professors with whom you have research, volunteering, or work-study experience with. If you don't have that, then the next best thing is probably a case where it was a class where you went to office hours and built some rapport with professors.
I'll say that it's usually the case for students that they have little rapport with most professors. This is why, to lower year students, I encourage you to cultivate rapport with some of your professors. Recommendation letters are relevant for grad school admissions and awards, so many people will need them down the line!
One last thing I'll add is that when you reach out to a professor to be a potential recommender, offer to meet with them in person to talk about the situation. This is especially useful in cases where the professor doesn't know you well. In this meeting, you can explain your motivation for applying to X, explain why you have the qualities that X is looking for, walk them through your resume, etc. This gives professors some content to actually write about in their letters! Otherwise, it will be extremely generic and they'll be forced to just use a template that they likely have saved on their computers.