The quest becomes available at 100% friendship or rivalry.
If you have completed Isabela's Regret, the cutscene begins with Isabela offering to sail with her. If Castillon was killed during No Rest for the Wicked, and she didn't get the ship, Fenris simply comments that she doesn't own one.
If Hawke was in a romance with Fenris in Act 2, then he will bring up the fact that they "had not talked about what happened between them three years ago." At this point, you will be able to question his reasons for leaving and choose whether to rekindle the relationship, or cut it off permanently. If Hawke slept with someone else after Fenris left, he will bring up this topic.
Fenris can leave party permanently at this point if you choose the option "You should leave". He will thank Hawke and state that he will go west.
If this quest is completed, Fenris will subsequently support Hawke during the climax of the story no matter what. If the quest is not completed, Fenris will initially refuse to go against his principles.