Every Lieutenant you own has a star rating, from 1 to 9. When you first receive a lieutenant, they are usually 1-star. Higher star levels are made by combining identical lower star level lieutenants, so two 1-star lieutenants can be combined into one 2-star lieutenant, two 2-star lieutenants can be combined into one 3-star lieutenant, etc. The maximum star level is 9 (which would require 256 1-star lieutenants).
Different lieutenants of the same rarity can be combined using Lieutenant Fusion, increasing the star rating of one while destroying the others.
This new way of calculating max Lieutenant level was introduced on April 18, 2013, after the Display Bug fiasco.
When lieutenants are combined, they retain their old level, but they are initially displayed as being level 1.
There are Achievements that can be earned by starring-up Lieutenants.