"Muad'dib" was the word in the Fremen language for the kangaroo mouse, a hardy l'il critter in any desert environment but on Arrakis also highly visible as a formation on its moon. The choice of this name, much like practically everything else Paul did, was seen by the Fremen as a sign that he was the one sent to lead them. See also: Usul, another Fremen name for Paul Atreides.