Option 1: Reference Speed
This is the quick and dirty approach (and the one I've used most). Effectively, you move the map at the same speed as one of the things on the map. That thing doesn't move, everything else moves around it.
For example, a ship moving north at 30 squares/turn, chasing another ship moving north at 25 squares/turn. The faster ship doesn't move, the slower ship moves five squares south each round.
If an unmoving object is dropped off the boat, it moves south at thirty squares / round.
If you're dealing with two ships moving relative to each other, you'll want the ship pieces to be printed on a separate sheet from the map itself, allowing you to move them (slowly and carefully) with the minis aboard.
This approach has two downsides:
If the ships are large relative to the characters, you'll run out of map space quickly. Turning ships becomes quite difficult.
If the ships are moving in different directions, figuring out final positions can get tricky.
Option 2: Cutouts
This is the more robust solution. Have maps of each individual ship, with the characters minis on those. These maps can either be a portion of the larger map, or (ideally) something separate that can be placed off to the side.
Your larger map represents the naval battle. Use a larger scale for this one, such that each ship is only one or two squares.
This way, you can have detailed character combats aboard each ship, without bogging down the naval battle. Calculating range from a character in one ship to another is fairly simple: distance from attacker to ship edge + distance between ships + distance from defender to ship edge.
Characters moving through "ship scale" squares round their movement down to the nearest ship-scale square.
Disadvantages:
Option 3: Simplify
This option questions whether or not you really need full tactical simulation at both scales. Pick a battle that's more interesting/important, and use the map for that. Reduce the other to a handful of rolls that you can intersperse throughout the combat.
Example:
The PCs are aboard a ship and plan on boarding their opponent. The game starts out with tactical ship combat.
Once the players board the opposing vessel, the GM determines which combat deserves the map. Generally, this will be the boarding. The less interesting combat is removed from the map, and the more interesting combat takes its place.
The boarding is run tactically as per the rules. For boarding actions that cross from one ship to the other (ranged attacks, teleportation, flight, etc.), make default assumptions about distance and heading to the other ship. Or roll for them.
Summarize the less interesting combat (the naval combat in this case) with die rolls. Make basic assumptions like "it'll take you about three rounds to get out of range" or "spinning around like you usually do, I can generally hit you about once every other round." Playtesting will help with these assumptions.
Disadvantages:
