Assuming the travelers had knowledge of any local very close binaries and could observe their relative motions, then a velocity relative to them would be somewhat easy to calculate. [This is borrowing from Galileo's idea to determine longitude using the positions of Jupiter's moons, plus adding a dash of Romer into it.
]