Can you use a fly speed underwater? How does the spell Overland Flight interact with underwater movement?
Fly speed won't help you at all while underwater.
Unless you have some kind of ability that allows your to use your fly speed while swimming, your different speed types do not help you on different terrains. Swim speed will not help you move on land or air, land speed won't help you move on water or air, and thus, fly speed won't make you run faster on land, nor make you swim faster on water.
Excluding the swim skill rules, which allow you to use half your base land speed as your movement rate, but does not grant you swim speed at all. But that's a specific rule for the skill.
To clarify, whenever a rule is talking about your speed or your base speed, it is a reference to a character's base land speed, not whichever speed is highest. This can be found on common game terms:
Base speed is your unencumbered speed for a specified type of movement. Your base speed for any movement type is calculated in a similar manner as described in Base Land speed. When a speed type is not referenced, base speed usually implies base land speed.
Here is the basic description of the three movement types:
Land speed is the normal mode of movement for creatures that do not burrow, climb, fly, or swim.
Creatures with a fly speed receive the Fly skill for free as a class skill.
A creature with a swim speed can move through water at its indicated speed without making Swim checks.
If we check the Fly skill description, it says:
You are skilled at flying, either through the use of wings or magic, and you can perform daring or complex maneuvers while airborne.
Finally, the Swim skill makes several mentions of your speed (and even your base land speed on the unchained rules), but nowhere it talks about using other speed types while underwater.
There are exceptions, of course. The Swim on Air spell allows a water-based creature to use her swim speed to fly as if swimming on air, for instance.
However, it isn't unheard of that a creature that could make more sense to use a certain speed type instead of another. Some water-based creatures have zero land speed, so the GM might have to give it at least 5 land speed when trying to do something extraordinary while on land, even though normally they cannot move on land at all. Or even house-rue to use a speed type as another if that would make more sense in a given situation.
Example, the Octopus has a special water-based movement ability called Jet, which allows them to move 200 ft in a direction, while this ability does not mention that it can be used on land (even if that doesn't make a lot of sense) it's perfectly fine to allow a flying octopus to use that ability while airborne.
It seems even Aquatic Adventures is silent in this regard, but creative director James Jacobs in this 2011 Paizo message board post says
Swim and Fly are not only different types of movement speeds… they're governed by entirely different skills.
Fly does not grant you any bonus or benefit to flight [likely supposed to be swim] at all. There are different spells (such as touch of the sea from Advanced Player's Guide) that grant you increases or bonuses to swimming. Fly does not.
(The same post is referenced again as late as 2015 here.) Nonetheless, ask the GM if a creature can use the higher of its land speed or its fly speed to calculate its movement when it makes Swim skill checks; the word speed is slippery in Pathfinder so a positive ruling combined with the spell overland flight may allow a creature to swim faster than normal.
Ask your GM.
This is something that I, for one, would absolutely houserule in just about every case. The way that a spell interacts with a circumstance it is not designed for (like trying to fly underwater) depends heavily on the way that magic works on the setting.
For instance, is the spell using some sort of repulsion effect to keep you off the ground? Or is it moving your absolute position relative to the nearest centre of gravity? Or maybe it is "pulling" against the weave of magic, or generating gravitons to make you "fall" upward, or some other method.
How it works is up to your GM and the design of your setting, which means that although the RAW may give you some indication, you can't rely on it in this case. Only once you know the underlying principles of the magic system in your world, can you decide how oddly-used spells will behave.