Hey Freedom, I would be happy to expand on some of these topics. Unfortunately I may not be much help on the internet issues, such as search engines, secure email, VPN and browsers. I do have first hand experience in vehicle and GPS data as well as how law enforcement is obtaining and using that data for prosecution.
GPS devices:
Most stand alone GPS devices record what is called a track log, which is basically a breadcrumb trail of points and time. This can show a history of movement that the device has experienced. Track logs can cover months to years worth of data and most devices are retrievable through free and open source software. Very few devices have this data encrypted (TomTom is the only one currently).
The only real way to remove any data you have set is physical destruction of the memory chip within the device.
There are numerous smartphone apps that allow navigation through GPS these days. The Garmin app stores track log data on your device. Google uploads your location information to their servers. I would recommend that if you do not want your movements recorded and tracked you use a standalone GPS device that is not connected to your phone. This results in a reasonable amount of privacy as you cannot be easily tracked remotely, but you must be very protective of that device. Whenever someone has physical access to the device there is potential to quickly and discretely copy that data.
In vehicle navigation/infotainment systems:
Many cars now have Bluetooth communications, embedded telematics, GPS, cameras, microphones, WiFi and more. ALL of these systems store data from these different components. Since they are communication capable it is possible to transmit some of that data externally. The only way to erase data from a car is physical destruction of the memory chip. I have recovered units from vehicles involved in severe impacts and subsequent fire followed by a dousing and left in a tow yard to corrode for a couple months. I have pulled the memory chips from damaged boards, placed into a surrogate module and recovered all of the data.
Some examples of what is recorded in the car: Contact list, Call Logs, Text (SMS) messages including body of the text, GPS track logs, stored locations, Complete file list of any USB device plugged into the vehicle (will show what files, file type, size, creator and any other metadata available), Phone BT addresses, device IDs and more.
I highly recommend that if you use rental cars that you do not pair your phone or plug into a USB jack for charging. Use a cigarette lighter to DC jack to charge your devices.
Many Law Enforcement offices and the FBI know about this data and will do everything they can to obtain it. Your digital property is the same as your physical property, you must guard it closely. Do not consent to any searches, physical or digital. Do not turn over any devices to anyone. You do not have to give anyone your passcode to unlock a device. Passcode lock every device that you can, but know that a code won't stop someone with the right tools.
I hope I was able to answer some questions. If there is more you would like to know I would be happy to help! -Dan