Your mileage may vary, but it shouldn’t take significantly longer than a couple of hours. If you’re not too unlucky, it should probably take just one hour, both when you’re publishing an app for the first time, and when you’re releasing an update for an existing app.
If it’s taking significantly longer than that (I’m talking more than one day here), you may have been fooled by Google’s peculiar requirements for deployments.
This fooled me twice (so I guess, shame on me).
When you publish an app for the first time, you need to create a Google Group or a Google+ community for testers before the link to your app becomes available. If you try to access the link (even using your own Google account) without being a member of the configured group/community, you’re greeted with a 404 page.
Last time I published an app though, setting an existing Google Group for testers (one that I had configured for a different app) didn’t seem to work. When I created a new Community on Google+, it worked right away. I don’t know if I was just unlucky or if you need a dedicated Google Group for every app, but if you still get a 404 after setting up the Google Group, just try with Google+.
After you’ve become a tester for the app (by visiting your app’s page on the Play Store) it usually takes another hour or so before the APK becomes available for download.