  Let $S$ be a birationally ruled surface. We show that the moduli schemes
$M_S(r,c_1,c_2)$ of semistable sheaves on $S$ of rank $r$ and Chern classes
$c_1$ and $c_2$ are irreducible for all $(r,c_1,c_2)$ provided the polarization
of $S$ used satisfies a simple numerical condition. This is accomplished by
proving that the stacks of prioritary sheaves on $S$ of fixed rank and Chern
classes are smooth and irreducible.
