You have to "prove" to be a US resident by accessing the store with a US based IP once. It's sufficient to use a US proxy.
Additionally, you need a US credit card with a US billing address to buy apps; to download free apps, you can fake the number (all 0's will work) and address. Then ensure 1-click ordering is turned on in your Amazon.com account (the Appstore will prompt you to do this and provide a link). A prepaid credit card in USD might be a good way to do this for people outside the US, I'm not sure.
Some users seem to be reporting that Amazon is now blocking non-US IP addresses. This isn't 100% accurate, since I access the app every day from Canada with no issues. It may block specific countries though, in which case you'll need a US-based proxy/VPN. Make sure you trust it, so that your account credentials aren't compromised; don't use Tor / Orbot!