I have an account with Hostgator, and have registered private name servers (ns1.mydomain.com and ns2.mydomain.com). How long should I expect to wait for those changes to take place? Should my website be unavailable during that time?
Typically no, most major registrars will implement NS updates very quickly (minutes, or just a few hours). What remains is the
The typical cache period is 4 hours, however ISP's are free to ignore that, and continue to serve the old IP sometimes up to 72 hours (in most cases). Effectively, some of your users will not realize that you switched until their ISP clears their resolver cache for your domain. I've tried flooring the TTL value on all A records and CNAMES weeks before changing without any kind of positive effect worth reporting.
When doing a switch, refrain from posting new content for at least 72 hours. Additionally, don't do a switch within 72 hours of posting new content, if at all avoidable.
Then again, it really depends on where your users live. Most US ISP's refresh (at least) once every 48 hours. While traveling around Asia, I've seen that process take up to two weeks (but we have to consider horribly configured proxies here).
Depending on your reach, soon after a change your new site and new content will be accessible to most, but some will get a 404. Some might not be able to resolve it at all, it all depends on who hits the ISP name servers (along with what ISP) and when.
Edit (and rather specific to just this question)
Your domain currently points to:
And a dig from public name servers points to:
Public NS's (maintained by Level3) are, in order:
And they obey the TTL's you set, at least in my experience. Please disregard the query times, I'm digging from across the globe while using TCP over carrier pigeon.
As a practical matter, I like using What's My DNS, an online tool that samples a number of DNS servers across the planet which will give some idea who's got what, where. It's a great way to get a kind of an answer to the question "has my DNS propagated?"