I just finished a game with them, and yes, you need to move your ship close to the barbarian ships (I think it usually occurred within 2-3 hexes of the ship, close enough to bombard). I actually created quite a huge navy by using this strategy, just sailing around and converting quite a few barbarian ships.