Every RTS i've ever played has a experiece based system for all units. Now I understand that cap ships have experience levels, however I believe we should make one for all ships and units.
I would model the expierence system after RTW, basically points were based off damage that unit caused. THere was 3 main levels and each level had 3 smaller levels. Experience meant many things, mostly in their ability to be more powerful.
Therefore I believe we should create a simliar system. I say make 3 levels that a ship can obtain. It can only obtain this by causing damage, if its a colony ship or scout ship it can also gain experience. Colony ships can earn experience by colonizing, scouts by discovering. Benefits overall would be faster, stronger, more powerful.
However colony ships and scout ships are a small part of your fleet.
I think this is how it should work, lets assume this
First level 10,000 damage done would gain you 10% over all stat increase
Second level 25,000 damage done, would gain you an additonal 10% over all increase
Third level 75,000 damage done would gain you an additonal 15% over all increase
So a fully upgraded fleet would be 35% stronger then its counterpart.