Firefox Sync stores your Sync credentials in Password Manager, so they're available across restarts.

If you have Firefox set to clear your passwords on exit, then your Sync account credentials have been lost, and you'll have to set up Sync every time you start Firefox. (I hope you saved your Sync Key somewhere!)

In order to have Sync persist across restarts, you need to disable clearing of passwords. I'm also uncertain what the behavior of Sync will be if you clear your history; it should work fine, but I've never tested it myself.

Thanks for the help! I disabled password clearing and now I seem to stay connected when I restart Firefox.