I think it took about an hour or two for me. Also, the direct link to the app in the store should work right away, it just takes some time for it to appear in the search results.
Based on experience: 0-4 hours for the direct link to work (from the Ready to sale email). 1-12 hours for search to work. 1-24 hours for it to appear on the new releases list.
Our numbers (3 apps) have been: roughly 1 hour for direct link 3-5 hours for search to work 4-6 hours before app shows up in category 5-8 hours before app shows up in RSS feeds