Gemara

Beraisa: R. Yochanan ben Zakai made nine enactments. One was that Kohanim may not ascend to bless the Tzibur while wearing shoes.

Sotah 40a - Chachamim: R. Yochanan ben Zakai enacted that Kohanim may not ascend to bless the Tzibur while wearing shoes. This shows that one should have fear of the Tzibur!

Suggestion: They may not wear shoes because this is disrespectful to the Tzibur.

Rejection (Rav Ashi): No. The concern is that a Kohen's shoelace will snap, and he will stop to tie it and miss Birkas Kohanim. People will think that he did not bless because he is a Pasul Kohen, e.g. he was born to a woman who was divorced or did Chalitzah.

Rishonim

Rif and Rosh (Megilah 16a and 3:23): One of nine enactments of R. Yochanan ben Zakai was that Kohanim may not ascend to bless the Tzibur while wearing shoes.

Rambam (Hilchos Nesi'as Kapayim 14:6): One of the enactments of Ezra was that Kohanim may not ascend the Duchan while wearing shoes. Rather, they must be barefoot.

Kesef Mishneh: The text should say it is an enactment of R. Yochanan ben Zakai.

Poskim

Shulchan Aruch (128:5): Kohanim may not ascend the Duchan while wearing shoes.

Mishnah Berurah (15): One must conceal his shoes in order that they will not be seen in the Beis ha'Keneses, for this is disgraceful. If one can remove his shoes without touching them, he can remove them after washing his hands.

Kaf ha'Chayim (30): If he can leave his shoes outside the Beis ha'Keneses without concern that they will be stolen, he should do so.

Shulchan Aruch (ibid.): They may ascend in knee-highs (socks).

Beis Yosef (DH veha''Rambam): The Rambam connotes that they must be barefoot. However, R. Mano'ach says that he only comes to exclude shoes.

Rema: Some are stringent if the knee-highs are of leather. The custom is to be lenient in some places.

Hagahos Maimoniyos (Tefilah 14:4): Avi ha'Ezri derives that they may ascend in knee-highs, because the only concern was that one stop to tie a shoelace that snapped.

Beis Yosef (DH v'Chosvu): This connotes that even leather knee-highs are permitted. However, sandals and shoes are forbidden even if they have no laces; Chachamim made a blanket decree. It seems more reasonable to say that leather knee-highs are not permitted; they are like sandals and shoes. However, even knee-highs that are not of leather are tied by garter straps near the knee. The same concern should apply! Perhaps we are concerned only regarding a shoe, for it is a disgrace for a sandal to be open (and the Kohen will surely fix it). An open knee-high is not such a disgrace, so the Kohen will not bother to fix it. Alternatively, the knee-highs permitted are trousers that go from the hips to the feet, in which there is no concern. The Chidush is that we do not say that they are included in R. Yochanan ben Zakai's enactment. He did not decree that they must be barefoot. The previous Perush seems correct; all knee-highs were permitted, except of leather. If the Heter was only for trousers, he would have specified.

Magen Avraham (5): It seems that leather knee-highs are forbidden only if they reach only to the knee and are tied by straps or cords. But if they reach to the hips they are trousers, and they are permitted. It seems that if they are cloth but covered with leather, they are permitted.

Kaf ha'Chayim (34): On Tish'ah b'Av, to pain ourselves we do not wear shoes. Cloth shoes covered with leather are forbidden, because they protect. Here, the concern is lest people come to permit shoes with laces; we are not concerned lest these be confused.

Mishnah Berurah (18): Our knee-highs are boots in which we walk through mud. One should not be lenient about them, for it is a disgrace to the Tzibur. The same applies to rubber galoshes. It is improper to go barefoot to the Duchan, since people do not go barefoot in front of Gedolim. Therefore, one should wear cloth socks. This is the custom.

Kaf ha'Chayim (31): We learn from Chagigah 13b that it is improper to go barefoot in front of Gedolim.

Kaf ha'Chayim (28,29): Also on Yom Kipur and Tish'ah b'Av when Kohanim were cloth shoes, they must remove them. Felt shoes are forbidden, unless the cold is harsh for them. However, this is only if they are not worn outside. Leather is forbidden even in such a case.