Is 5V too much for a device that uses 3.5V?
The datasheet didn't say much. I know it's the wrong model (AirMap 500), but still, no internal images. And the input power just said 3V. 

Well, if I were you, I would either A, open the GPS and look inside and look for a Linear Voltage Regulator. If you find it then it's pretty safe to hook it up to a 5V input. 

Or B, connect the cigarette lighter plug to a 5V supply and see if it still outputs 3.5V, if it does then I'd see if the GPS works with it as well.

Or C, get a Linear Voltage Regulator that converts 5V to 3.3V and burn off the excessive voltage×current in the form of heat. 

Or D, get a step-down converter from 5V to 3.3V.

Or lastly, E, take my bets and connect it up to 5V and hope for the best.