Originally Posted by ThePoloHobo
I am rather handy at programming, do these gps chips require any sort of paid service?
Nope, you just need some solid programming. The main obstacle you have to overcome is how to broadcast the position updates so you can find it, so you will need some sort of data connection somewhere. You can hope for an open WiFi AP that a WiFi shield would connect to, but that would be sporadic at best. Edit: Nothing else is immediately jumping to mind actually, so you may be stuck with carrier based data (cell).
And, of course, if they ditch the case well, you won't recover a whole lot.
Here's the Arduino shield I would recommend: http://www.adafruit.com/products/1272
And I'd use an Uno R3: http://www.adafruit.com/products/50
I've used that with good success, but never via battery power, always from a constant source.
The programming shouldn't be too difficult - there's actually a lot of examples out there that will get you 75% of the way there.
Edit2: They make GSM shields as well, which can serve as your data connection, assuming you have a SIM card with a carrier. The shield alone is like $110 (youch!), plus whatever carrier costs. All that to have a system much like a phone sitting in there - but with more extensibility and options to you.