In the licensing documentation the android developers mention an easy way to more or less securely identify an android device. They are using android.Settings.Secure.ANDROID_ID.
They say they query the system settings for this. But they don't explain this any further.
How do I obtain the android_id and do I need special permissions for doing so?
It's all in the Javadoc, as linked to by this question you edited 30 minutes before this one! :)
http://stackoverflow.com/questions/2785485/is-there-a-unique-android-device-id
The "Secure" part just means that apps can't write to it, only read. I seem to recall that this device ID isn't always present; it's populated by the Market as required, perhaps.