I posted a photo of Nelson Mandela in a kufiya on December 21, 2012. He was wearing it Algiers, which he visited in May 1990 to see his former FLN contacts, who gave him and his comrade Robert Resha (d. 1974) military training in Morocco in March-April 1962.
Since Mandela's death this photo of him in Oujda, Morocco in March 1962 has been circulating a lot.
Mandela is in the second row, wearing shades. The man in front of him, in the brown sports jacket, is Ahmed Ben Bella, first President of Algeria, from 1963-65. He was deposed by the man with the mustache, wearing a tie and a light overcoat, Houari Boumedienne, who served as Chair of Algeria's Revolutionary Council from June 1965 to December 1976, and from then until December 1978 as Algeria's second President. (It may be Amilcar Cabral of the PAIGC standing between Boumedienne and Ben Bella.)
(As an aside, I'm glad that Mandela and the ANC did not adopt the policy toward Jewish South Africans that the FLN took toward Jewish Algerians.)
Mandela stated, on his arrival in Algeria on a state visit in 1990 that "it was the Algerian army [i.e., the Algerian Liberation Army] that made him a man."
Here's a photo of Mandela (center), his ANC comrade Robert Resha, and his trainer Mohamed Lamari. (For some reason several Algerian sources identify Resha mistakenly as Hamilcar [sic] Cabral. Amilcar Cabral was the leader of the Guinea-Bissau and Cape Verde national movement for independence, the PAIGC.) Lt. Gen. Lamari was part of the officer corps that overthrew Algerian President Chadli Benjadid in 1992, and he became the army Chief of Staff in 1993, a position he held until 2004. That is, he was the head military man during the bloody Algerian civil war. As head of the army, and as an "eradicationist," that is, someone who rejected any negotiation with the Islamist opposition. No doubt he was responsible for numerous war crimes.
Read more about Mandela and Algeria here (in French).