The term "Almoravid" comes from the Arabic "al-Murabitun" (المرابطون), which is the plural form of "al-Murabit"—literally meaning "one who is tying" but figuratively meaning "one who is ready for battle at a fortress". The term is related to the notion of Ribat, a frontier monastery-fortress, through the root r-b-t (ربط "Rabat": to tie to unite or رابط "Raabat": to encamp).
The name "Almoravid" was tied to a school of Malikite law called "Dar al-Murabitin" founded in Sus al-Aksa, modern day Morocco, by a scholar named Waggag Ibn Zallu. Ibn Zallu sent his student Abdallah ibn Yasin to preach Malikite Islam to the Sanhaja Berbers of the Sous and Adrar (present-day Mauritania). Hence, the name of the Almoravids comes from the followers of the Dar al-Murabitin, "the house of those who were bound together in the cause of God." 
It is uncertain exactly when or why the Almoravids acquired that appellation. al-Bakri, writing in 1068, before their apex, already calls them the al-Murabitun, but does not clarify the reasons for it. Writing three centuries later, Ibn Abi Zar suggested it was chosen early on by Abdallah ibn Yasin because, upon finding resistance among the Gudala Berbers of Adrar (Mauritania) to his teaching, he took a handful of followers to erect a makeshift ribat (monastery-fortress) on an offshore island (possibly Tidra island, in the Bay of Arguin). Ibn Idhari wrote that the name was suggested by Ibn Yasin in the "persevering in the fight" sense, to boost morale after a particularly hard-fought battle in the Draa valley c. 1054, in which they had taken many losses. Whichever explanation is true, it seems certain the appellation was chosen by the Almoravids for themselves, partly with the conscious goal of forestalling any tribal or ethnic identifications.
The name might be related to the ribat of Waggag ibn Zallu in the village of Aglu (near present-day Tiznit), where the future Almoravid spiritual leader Abdallah ibn Yasin got his initial training. The 13th-century Moroccan biographer Ibn al-Zayyat al-Tadili, and Qadi Ayyad before him in the 12th century, note that Waggag's learning center was called Dar al-Murabitin (The house of the Almoravids), and that might have inspired Ibn Yasin's choice of name for the movement.
Contemporaries frequently referred to them as the al-mulathimun ("the veiled ones", from litham, Arabic for "veil"). The Almoravids veiled themselves below the eyes with a tagelmust, a custom they adapted from southern Sanhaja Berbers. (This can still be seen among the modern Tuareg people, but it was unusual further north.) Although practical for the desert dust, the Almoravids insisted on wearing the veil everywhere, as a badge of "foreignness" in urban settings, partly as a way of emphasizing their puritan credentials. It served as the uniform of the Almoravids. It was worn in remembrance of the Sanhaja's escape from Yemen disguised as women, thus making it simultaneously an indication of their faith. Under their rule, sumptuary laws forbade anybody else from wearing the veil, thereby making it the distinctive dress of the ruling class. In turn, the succeeding Almohads made a point of mocking the Almoravid veil as symbolic of effeminacy and decadence.