>a device when it is first powered on can broadcast out looking for other Amazon WiFi devices in the home and receive the credentials from them.

Ah! That explains it. I was going to be really skeptical that other people's wifi endpoints would "help out" foreign devices, but this makes more sense.