Simple Failover markets itself as:
continuously monitors your servers to find out which are up and which are down, and then it dynamically updates your DNS records accordingly so that your domain name always points to a functional server.
From what I know, updating DNS records can take hours to days to propagate. As such, even if they dynamically update my server's DNS records, my users would still have to wait a few hours before they would see any change right?
If so, how could "Simple Failover" work?
DNS record lifetimes are based on the TTL (Time To Live) of the record itself. If the TTL is 1 hour then theoretically that's the maximum amount of time a DNS resolver will cache that information before it performs a new lookup for the record. Typically this would only affect DNS resolvers that already have the information in their resolver cache. Any resolver that doesn't have the information in their cache will perform a lookup and get the updated/new information immediately, since the information is not in it's cache there's no waiting for the TTL to expire.
Others are bound to warn you that some DNS servers don't honor TTL's and that certainly is a possibility. I prefer to work from the assumption that all DNS servers will honor the TTL and I'll deal with any edge cases that come up. If you start worrying about what some DNS servers may or may not do then you'll get all wrapped up in trying to troubleshoot DNS problems that aren't actually your problem. If someone else's DNS server doesn't honor my TTL then that's their problem, not mine.
As an aside: DNS is a pull technology, not a push technology. DNS records don't get propagated, as is commonly stated (or mistated). The only name servers that hold a copy of your DNS zones (and the records in those zones) are your name servers. When you make a change to your DNS, that change does not get pushed anywhere. Other DNS servers and/or resolvers may have one or more of your DNS records cached but when the TTL expires they'll pull the updated/new information the next time they perform a lookup of that particular DNS record.