How do CFD programs model a propeller?

Various methods - pressure increasing disk - to CFDing the propeller blade itself?

It depends what you want to do. In most cases one will model the propeller per se and set a multi-frame of reference case. With CFX I have seen modelled the full hull, the propeller and the free surface; this is important as for boats the interaction between propeller and hull can be fundamental (or propeller and pod).

In some cases, say a big water treatment tank or a mixing vessel maybe, you may represent the stirring effect of blades via a source term, although this might not always work well, eg if the baldes are close to walls or if the blades occupy a significant volume in the vessel etc.