Part-based creatures are those whose bodies are composed of parts that can be changed independently of the others. Specifically, instead of having a single model for the entire body, a part-based creature has a model (or two models, when there is a "left" and "right") for each of the head, neck, torso, pelvis, biceps, forearms, hands, thighs, shins, and feet. In addition, the exact models used by part-based creatures depends on gender (which is not the case for other creatures).
Being part-based is a function of appearance, and there are only a limited number of part-based appearances available, typically those for the playable races. (Player characters are by default part-based, and it is probable that the ability to make non-player characters part-based was more side-effect than goal.) Furthermore, not all appearances for a given race are part-based. For example, while there is a part-based appearance used for human player characters, there are also thirty non-part-based human appearances available.
The most notable feature of part-based creatures is that their parts are replaced by the corresponding parts of whatever clothing, armor, and helm they have equipped. Part-based creatures are also capable of having visible cloaks (starting in patch 1.68). The ability to have tattoos is also a result of being part-based, as is the bone arm of a pale master.