Etymology: from Provençal ahl (garlic) + òli (oil).
Like mayonnaise (generally composed of oil, egg, and vinegar), aioli is an emulsion (a mixture of unblendable liquids).
There is a Catalan variation (allioli) which uses no egg. In this version the garlic is completely mashed and the olive oil is slowly drizzled in while the mashing continues. Creating an actual emulsion this way is quite difficult; the egg makes it easier.
The basic idea has been around for a long time. Apparently, Pliny the Elder (A.D. 23-79) referred to a very similar substance: when garlic is “beaten up in oil and vinegar it swells up in foam to a surprising size".