You need maintenance facilities - either on the planet or through maintenance modules on ships. Each facility can support x tons of military shipping - it's just a matter of building enough facilities so that your supported number of tons is greater than the fleet currently stationed there.
Manned installations on the planet will also produce MSP, if you have the minerals they need (Duranium, Uridium, Gallicite).
If you've got some facilities (but not enough to fully support the fleet) then your ships deployment time will be slowed down by a %, rather than stopped.