What is "b'Gei Tzalmaves"?
Rashi: It is a dark land. This refers to Midbar Zif (Shmuel I, 26:2). Dunash said that every Tzalmaves is dark.
Radak: This is a dangerous place, like Gei Tzalmaves; Tzalmaves is the grave, a place of darkness - "Eretz Choshech v'Tzalmaves" (Iyov 10:12).
Why did David not fear evil?
Radak: It is due to his great trust in Hashem, "Ki Atah Imadi", like with all who seek You.
Malbim: It is "Ki Atah Imadi" - the Shepherd goes with him to guard him.
What are "Shivtecha u'Mish'antecha", and how do they console him?
Rashi: Shivtecha are afflictions. Mish'antecha is my reliance on Your Chesed. They console me that I will be forgiven for my sin.
Radak: This is based on the metaphor of a shepherd. He conducts the flock with a staff, and leans on it when he stands [still]. Even though they are one, it says Hemah, for it was called two names. For David, Hashem's Chesed and Tzedek were a staff and support, and a consolation from all afflictions - the staff when he went, and the support when he stood still.
Malbim: Shivtecha is a small stick to hit the Seh to return it to the path. Mish'antecha is a strong staff to chase away animals that would tear or destroy the Seh. When I see them, I know that no harm will befall me. This is a parable; afflictions are for his benefit, to guide him to the good path. Hashem is his staff to save him from all his enemies.