domain name system - How long does it take for DNS records to propagate?

This is a Canonical Question about DNS Propagation

How long does it take for an the various types of records to propagate?
Do some propagate faster than others?
Why does it take time for DNS records to propagate and how does it work?