5 players and 1 Narrator. There were times when we played with 6 players and 1 Narrator, but that was a little bit too exhausting. From my experiences I think that the perfect number of players is 4.
For Star Trek campaigns, it's virtually impossible to give everyone something to do in a single episode (how many times have you seen an ep where certain characters only make a short appearance?), so you definitely don't want to go the route of trying to fill all of the dept. head spots with PCs.
I would recommend 3-4 players for a ST campaign, leaving the CO as an NPC. If you're running a smaller ship, I would suggest that all characters be department heads, since they'll usually be a lower rank anyway (you might have ensigns and lts. j.g. as DH's on the really small ships). On a larger ship, its easy to have non-department heads and even enlisted types in your group, making for a neat little clique of characters who seem to hang around each other all of the time.
Davy Jones
"Frightened? My dear, you are looking at a man who has laughed in the face of death, sneered at doom, and chuckled at catastrophe! I was petrified."
-- The Wizard of Oz