I think here the best available thing would be write your Android App or Use the Amarino its opensource and it already configures android to send values to Arduino, so edit this code to add a GPS library in the code and implement storing of gps data in variables that can be then further sent via. Bluetooth to your arduino.This is the best because you have something to start with as you not start baseless , you atleast have a communicating facility with this option you just need to gather GPS data and send it using the respective library.
for this you need to have some development experience in Eclipse with JAVA only as c++/c is not supported as core modules under android development.
Even if you want to implement what MarkT is saying then also you need to develop in Eclipse or other Android supported IDE in mainly JAVA only.