Site News - Outage?

A question for people have their own domains: I'm switching to a different web host and I was wondering how long it took to change DNS settings? I've heard some horror stories about sites being down for a while, and since I have an ad running right now, I don't want Loaded Mouth to be down for an undetermined amount of time. How much of a horor story am I looking at?

...oops, fucking around with the DNS settings caused me to change it. Says it will take 24-36 hours. I'm downloading everything from LM to my laptop and uploading it to the new host. Let's hope all the permalinks stay "perma."