What should I be doing now to get a good recommendation letter as a graduate student?
One suggestion is to get a good teaching reference if you're working as a TA.  Most departments have one or more faculty who supervise graduate student TA's.  If you're actually leading a recitation section or teaching a class, you should ask this person if they would be willing to write a recommendation letter addressing your teaching and you should invite them to observe you in the classroom environment.  A good letter of this support together with good student evaluations will make a strong case for your ability as an instructor.