In the High.txt file:
MakeUnit:: ID_CONSTANTINOPLE Galley 1 CATHOLIC_CULTURE //FN_REBEL
Rebels can be gifted ships at the start. I think the reason rebel ships aren't usually seen is that rebel provinces rarely are built up to the level necessary to produce them. And as we all know, the port is usually the first thing destroyed on invasions.