Combat experience you receive for winning fights, especially when you damage enemy ships or board them. Still, even participating in a fight usually earns one additional star for your crew so five fights with no crew losses and you get max level.
Navigational experience you get for entering ports and travelling distance on the strategic map.
From Data/AI/combatexperience.txt:
So a ship with a crew with five stars in combat has 70% more crew while boarding, reloads cannons 50% faster, does 50% more damage, receives 30% less damage from enemy and has 60% bigger morale.
A ship with a crew with five stars in navigation is 40% faster, turns 25% better, has 40% better range (less ports you need to enter to resupply) and has 40% better view range.
Navigational experience you get for entering ports and travelling distance on the strategic map.
From Data/AI/combatexperience.txt:
// combat experience level effect values
// Boarding crew amount (Level0 - Level5)
Level_0_BoardinCrew = 1.0
Level_1_BoardinCrew = 1.10
Level_2_BoardinCrew = 1.15
Level_3_BoardinCrew = 1.25
Level_4_BoardinCrew = 1.40
Level_5_BoardinCrew = 1.70
// Cannons load time (Level0 - Level5)
Level_0_CannonsLoadTime = 1.0
Level_1_CannonsLoadTime = 0.95
Level_2_CannonsLoadTime = 0.90
Level_3_CannonsLoadTime = 0.80
Level_4_CannonsLoadTime = 0.70
Level_5_CannonsLoadTime = 0.50
// Cannons damage (Level0 - Level5)
Level_0_CannonsDamage = 1.0
Level_1_CannonsDamage = 1.05
Level_2_CannonsDamage = 1.10
Level_3_CannonsDamage = 1.20
Level_4_CannonsDamage = 1.35
Level_5_CannonsDamage = 1.50
// decrease (own) crew damage from enemy fire (Level0 - Level5)
Level_0_CrewDamage = 1.0
Level_1_CrewDamage = 1.0
Level_2_CrewDamage = 0.95
Level_3_CrewDamage = 0.90
Level_4_CrewDamage = 0.80
Level_5_CrewDamage = 0.70
// morale (Level0 - Level5)
Level_0_Morale = 1.0
Level_1_Morale = 1.10
Level_2_Morale = 1.20
Level_3_Morale = 1.30
Level_4_Morale = 1.40
Level_5_Morale = 1.60
// navigation experience level effect values (Level0 - Level5)
// Speed (Level0 - Level5)
Level_0_Speed = 1.0
Level_1_Speed = 1.05
Level_2_Speed = 1.10
Level_3_Speed = 1.15
Level_4_Speed = 1.25
Level_5_Speed = 1.40
// Turning Arc (Level0 - Level5)
Level_0_TurningArc = 1.0
Level_1_TurningArc = 1.0
Level_2_TurningArc = 0.95
Level_3_TurningArc = 0.90
Level_4_TurningArc = 0.85
Level_5_TurningArc = 0.75
// Move range (Level0 - Level5)
Level_0_MoveRange = 1.0
Level_1_MoveRange = 1.05
Level_2_MoveRange = 1.10
Level_3_MoveRange = 1.15
Level_4_MoveRange = 1.25
Level_5_MoveRange = 1.40
// View range (Level0 - Level5)
Level_0_ViewRange = 1.0
Level_1_ViewRange = 1.05
Level_2_ViewRange = 1.10
Level_3_ViewRange = 1.15
Level_4_ViewRange = 1.25
Level_5_ViewRange = 1.4
So a ship with a crew with five stars in combat has 70% more crew while boarding, reloads cannons 50% faster, does 50% more damage, receives 30% less damage from enemy and has 60% bigger morale.
A ship with a crew with five stars in navigation is 40% faster, turns 25% better, has 40% better range (less ports you need to enter to resupply) and has 40% better view range.