Ha! Found the problem. By default Fedora uses socket activation to start the docker service. My server would reboot, nothing would touch the docker socket and so the docker service wasn’t running. As soon as I ran any docker command the service would come up.
Easy fix: systemctl enable docker.service