Joe is pointing out that if you haven't already replaced your domain's NS servers with the domain registrar, you need to do that before anything will take effect (AWS's servers must be your authoritative NS servers for your domain).
So a whois for your domain should then show you the new name servers, once propagated. They should look something like this near the bottom of a whois:
Name Server:NS-1315.AWSDNS-36.ORG
Name Server:NS-99.AWSDNS-12.COM
Name Server:NS-765.AWSDNS-31.NET
Name Server:NS-1970.AWSDNS-54.CO.UK
Once that's set, whenever you create new records in your zone they should become visible within a short period after some propagation. For example, if you just bought a domain on GoDaddy, created a stub zone in Route53 for your domain and take the NS server values they assign you and drop them back into the domain record with GoDaddy, any new records you add should be visible within 15-20 mins normally, or perhaps up to an hour.
The process of propagation, however, is entirely out of your hands once you've published new values. So you should always make smart use of TTL.
To make sure your values have propagated, you should get comfortable with the command line and use a tool like dig or nslookup to check:
dig host.domain.com
Should give you a result like this. My command is on the first line:
myhostmachine ~ # dig www.acme.com
; <<>> DiG 9.7.3 <<>> www.acme.com
;; global options: +cmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 9821
;; flags: qr rd ra; QUERY: 1, ANSWER: 1, AUTHORITY: 0, ADDITIONAL: 0
;; QUESTION SECTION:
;www.acme.com. IN A
;; ANSWER SECTION:
www.acme.com. 16390 IN A 216.27.178.28
;; Query time: 30 msec
;; SERVER: 8.8.8.8#53(8.8.8.8)
;; WHEN: Thu Dec 13 11:53:09 2012
;; MSG SIZE rcvd: 46
And nslookup would look like this. My command is on the first line:
myhostmachine # nslookup www.acme.com
Server: 8.8.8.8
Address: 8.8.8.8#53
Non-authoritative answer:
Name: www.acme.com
Address: 216.27.178.28