he should make several full stacks and several full fleets, then embark- but make sure the settlement that you capture to make the fleets has a port that can make ships- imagine fighting a very costly battle then discovering you cant make ships!