i know att was all over the news for recording gps information without permission. android was mentioned for doing the same but apparently it was opt-in or opt-out.
the first thing i would do is call the phone. perhaps it was left in lost and found. if not, you can try calling your carrier and see if they help you out. if someone stole the phone and doesn't plan on returning it there isn't much they could do besides brick the phone to prevent use. they aren't going to send authorities out to track down and locate the person.