I think it also depends on where in the world you are accessing the Play Store from. I have experienced my listing going live about less than 1 and a half hours after publishing it.
In my experience my apps have been there within an hour, but I wouldn't start to worry until at least 24 hours. I have also found that I could access my apps via their direct link much sooner that I could via search results.
Comments
mark.