If you killed Jonathan and the quest log says something like "Gareth left Paradise Downs" you won't find him again until after you set sail. He will show up in Act 3.

I'm pretty sure you can only sail w/ Gareth if you went the forgiveness route.