The best approach would be to have the location tracking feature switched off by default and allow it to be switched on in the settings and perhaps present user dialogs asking for it to be switched on.
If your application requires it in all use cases, make sure that there is a notification at start-up that warns the user all future uses of the application will collect location data.
In general, a EULA is supposed to be designed to protect you, not gain permission from users.
The users have already agreed to the terms of the Market which include your application being able to see their location if they install your application.
Remember, they already give you permission in two ways:
- Your application indicates the permission in the manifest and therefore at install-time, so they know it when they install your application
- They have the option to switch off location detection in the settings via networks and GPS at any time
To conclude: You should include a notice, but not an entire agreement as it is unnecessary. A notice is courteous enough. You do not require their permission as long as the phone is being used in a country Google may legally perform business in.