The criteria should be quite simple:
a) to be FM or above. It's not worth taking lessons from someone below this level since you might end up wasting time by learning wrong things. I also think that FIDE doesn't recognize as coaches those who don't have the master title.
b) you should be able to communicate with him effectively.
Being a titled player has no relationship to teaching and those that prescribe to that opinion are wrong or confused. Plenty of players with lower then a FIDE given rating(s) are fully competent in teaching. Some people are good players and some are good teachers. Communication is the key and that can be a difficult job considering the international-ism of the net. Just because one has a title means nothing. Being committed, passionate and able to communicate concepts is important, but it all revolves around what the student wants and he must be able to communicate their wants succinctly!
4) he should (in addition to the teaching skills mentioned above) actually enjoy teaching and not only do it to pay his bills.
An important point everybody missed ... thanks for pointing that out!