Gemara

(R. Yitzchak): A tradition from Moshe from Sinai requires the straps to be black.

Menachos 35a - Question (Beraisa): Tefilin must be tied with their own Min (kind), whether the straps are Yarok (yellow, or perhaps green), black or white;

Red straps may not be used, due to disgrace and another reason.

Answer: R. Yitzchak requires the (side of the straps that face) outside to be black. The Beraisa permits the inside to be Yarok, black or white.

Question (Beraisa): ...Due to disgrace and another reason.

Other people do not see the inside. There is no disgrace or suspicion!

Answer: Sometimes the straps flip over, and the inside faces out.

35b (Rav Nachman): Their beauty must face outside.

Rav Ashi's straps became flipped over.

Mar Zutra: Don't you agree that their beauty must face outside?!

Rav Ashi: I didn't realize that they were flipped over.

Rishonim

Rambam (Hilchos Tefilin 3:14): A tradition from Sinai requires the straps of the Shel Rosh and the Shel Rosh to be black. The back of the straps face inside, so they are Kosher [even] if they are Yarok or white. One should not make them red, lest they turn over and it will be disgraceful. The back of the strap must be like the boxes, be it Yarok or white. It is beauty for Tefilin that the boxes and the entire straps be black.

Beis Yosef (OC 33 DH v'Chasav ha'Rambam): The Rambam means that the back of the strap should be like the box. The face (outside) must be black! The beauty is for Tefilin to be totally black, i.e. the boxes and both sides of the straps. This is not the custom.

Keren Orah (35a DH Leima): The Rambam explains "one must tie them with the Min of the boxes", i.e. the straps must be the same color.

Rashi (35b DH v'Noyeihen): The straps are smooth on one side and dyed black. This is their beauty. A proof is from Rav Ashi's strap, which turned over. Mar Zutra said that the beauty must face outside.

Tosfos (35a DH Retzu'os): Some make the boxes from white parchment. Only the straps need to be black.

Poskim

Shulchan Aruch (OC 33:3): Straps of leather or parchment are Kosher. A tradition from Sinai obligates the straps to be black on the outside, but on the inside he makes them any color he wants, other than red, lest people say that they became red from blood of his boils.

Mishnah Berurah (19): Baruch she'Amar connotes that it is a Mitzvah to blacken the straps until they are as black as a raven. If over time the blackness faded, one must blacken them again. This is very prone to happen where the knot is made tight. One must be very careful about this.

Mishnah Berurah (20): They must be black on the side of [the hide from which came out] the hair, which is the smooth side. If he blackened the inside, it does not help. He must blacken the outside.

Mishnah Berurah (21): One need not dye the inside at all. The Rambam says that one must blacken them like the boxes, but we do not hold like the Rambam.

Bi'ur Halachah (DH veha'Retzu'os): The straps of the head and hand Tefilin must be black. I am unsure. Perhaps mid'Oraisa it suffices for the required Shi'ur for the straps to be black, and the rest is merely to beautify the Mitzvah. Or, since it is all connected, the entire strap must be black. A support for this is the question from the Beraisa that permits straps of other colors. We did not answer that what is past the required Shi'ur is from other colors. This would have been a better answer, for it would avert the Gemara's next question, that there is no disgrace or suspicion due to the inside! We can reject this. The Gemara was sure that mid'Rabanan, we do not allow two colors on one side of the strap, for it looks spotted. This requires investigation.

Note: This shows that at least mid'Rabanan, the entire strap must be black.

Bi'ur Halachah (ibid.): Also, I am unsure whether the tradition from Sinai applies to the piece of the strap that enters the Ma'avarta (the extension of the box, through which the strap passes). L'Chatchilah, surely one must blacken it, lest it come out of the Ma'avarta. B'Di'eved, perhaps this is like the inside (rough side of the strap); see the Rambam.

Bi'ur Halachah (ibid.): Baruch she'Amar says that one blackens the strap, and after it dries a little, he blackens it again a second time, and a third time, until the leather is sufficiently black, like a raven. I say that this is a mere Mitzvah. Letter of the law, it suffices that they are called black. Therefore, even if it resembles blue, it is Kosher. We learn from Nidah 19a. If [blood] is as black as Cheres (vitriol, used to make ink), it is Tamei. Anything fainter is Tahor, even if it is black like blue. This shows that blue is a shade of black. We find this also in Chulin 47b and the Rambam (Hilchos Shechitah 7:19), regarding the lungs. Surely, l'Chatchilah the straps should be truly black.

Bi'ur Halachah (DH mib'Chutz): Do not say that it suffices to blacken whichever side he wants to wear facing out. Rashi said Stam that one blackens the smooth side. He did not say that this is the ideal Mitzvah (to wear the smooth side facing out, and if so he must blacken it). Also the Tur says so. The Pri Megadim says that if a Nochri dyed the strap, and one has no other strap, he should blacken the other side and wear it facing out. He explains that Menachos 35 discusses whichever side he will wear facing outside. The ideal Mitzvah is to wear the smooth side facing out. He brought a proof from Rashi, but Rashi holds oppositely! The Rambam connotes somewhat like the Pri Megadim. Surely, l'Chatchilah he (the Pri Megadim) agrees [that the smooth side must be black], like he himself wrote. The Pri Megadim causes a great stringency. If where the [strap] surrounds [the head, or the first time around the arm,] the black side faces out, he was not Yotzei and the Berachah was l'Vatalah. (The Bi'ur Halachah holds that it is Me'akev to blacken the smooth side, but it is merely Hidur Mitzvah that it face outside.) Poskim argue about this. The Eliyahu Rabah brought so from Gilyon ha'Mordechai. I say that the Beis Yosef disagrees, and says that he transgresses only the beauty being outside. Therefore, even if it turned over afterwards, it is forbidden.

Halichos Shlomo (4:28): Tefilin must look black; we are not concerned if points are not black.

Divrei Chachamim (39, citing the Steipler, ha'Gaon R. Y.S. Elyashiv Shlita and ha'Gaon R. C.P. Scheinberg Ztz"l): One white spot seen without scrutiny disqualifies.

Shulchan Aruch (4): It is good that a Yisrael blacken them Lishmah, and not a Nochri.

Beis Yosef (DH v'Chasav): Sefer ha'Terumah says that a Yisrael must blacken them l'Shem Tefilin. In Siman 191, the Tur was unsure whether a Nochri can do so alone. Since we learn from a tradition from Sinai, perhaps it must be Lishmah, like spinning strings for Tzitzis. One who is stringent will be blessed.

Magen Avraham (5): The Mechaber holds that Lishmah is not Me'akev. Sometimes the Rema argues, but he does not explicitly say so.

Mishnah Berurah (22): Most Poskim hold that it is a mere Mitzvah for the boxes to be black. It is not Me'akev (32:40).

Mishnah Berurah (32:184): One should be stringent, but if he cannot, he relies on the lenient opinion, lest he neglect the Mitzvah.

Rema: B'Di'eved it is Kosher if he (a Nochri) blackened the boxes, but the straps are Pasul even b'Di'eved.

Taz (5): There is no tradition from Sinai that the boxes must be black.

Magen Avraham (6): Even if he did not blacken the box at all, it is Kosher.

Magen Avraham (7): If a Yisrael later blackened them Lishmah it is Kosher. This is like Hash-m's name written Lo Lishmah. One may write over it Lishmah (Gitin 20a).

Mishnah Berurah (24): Many argue with this. The Pri Megadim suggests dying the other side. This is only if he has no other straps, like I wrote above.

Bi'ur Halachah (DH Pasul): I say that the Yisrael can dye them red or another color. This is Mevatel the black, like it says in Gitin 19a. Then, he blackens them Lishmah on top of the red. However, we say so only regarding writing. This requires investigation.

Mishnah Berurah (23): The Pri Megadim says that a child should not do what is Me'akev in Tefilin itself - the boxes, the knot, the Shin, and sewing them. This is even if an adult supervises and tells him to do so Lishmah. Also a woman should not do these. She may blacken the straps, for this is not part of the Tefilin themselves, for she knows to do Lishmah. A Nochri or minor may do so with adult supervision.

Bi'ur Halachah (DH u'Mihu): Surely one may be lenient about the boxes [that a Nochri blackened] to allow a Yisrael to blacken them Lishmah.

Teshuvos v'Hanhagos (3:21): One must be careful lest ink drop from the brush by itself, for this is not Lishmah, and it does not help to paint over it.