Much, much easier. Medieval Navigation techniques depended on two factors - a sextant to a known star, which determines your latitude. And accurate timekeeping, which combined with known star movements gives you your longitude. However, with a tidally locked planet, you can use that for both longitude and latitude - each position on the sea will have a unique location in relation to the gas giant. Gas giants tend to have visible cloud bands, so you don't need a red spot - you can determine the top and bottom from the gas giant's visible rotation by observing it for a short period, then calculate your exact position based on two sextant measurements.
Very importantly, sailors will be able to take these measurements during the day as well as at night.
It might be slightly easier, but there won't be any substantial differences. If there are other moons around the planet, they will likely be extremely bright. Therefore they would make excellent known markers, and navigators would likely determine their location off of visible moons instead of using stars (except in rare cases when all other moons are eclipsed or below the horizon).
Edit: it occurs to me that you can likely use sky glow to help navigate for portions of the dark side. Depending on exactly how bright the gas giant is, there will be a border area where it's not actually visible, but you can tell from the sky which direction the gas giant is. This won't be enough by itself, but it will let you determine your approximate longitude based on the brightness, which negates the need for timekeeping - a substantial benefit.
Edit2: Notes on Libration, based on comments. Libration is the "wobble" of another celestial body. For example, from Earth the moon will appear to rotate slightly as the day goes by, grow smaller and larger on a monthly cycle as the distance from the gas giant varies, and also "nod" slightly up and down on a monthly cycle.
Thankfully for our navigators here, we can ignore the first Libration component - because we're on the tidally locked body, we won't see the gas giant "turn" slightly as the day goes by. That means we only need to care about the "nod" (the gas giant appearing to move up and down slightly), and it growing smaller and larger. Fortunately for us, these variations are cyclic, and therefore predictable.
We can use measurements of the gas giant to determine where we are in the Libration cycle. For the "nod" we can measure the curve of the cloud bands on the gas giant. For the size, we measure the arc size in the sky using trigonometry. Combining the two, along with a date, should be sufficient to give good corrective values for navigation. So we don't need time keeping for this - we can get away with tracking the date, which is much easier to handle.