Are Florida, USA, roofing contractors required to have permission from everyone listed on the deed
I believe @brhans is right.  You don't need to have anyone on the deed of a house involved in the work of said house by any state law.  However some states may require some documentation for a contractor to possess a lien on the house.  

For instance if your dad's roof started leaking and he needed to fix it ASAP, no one would require your mom's signature on it.  To take it a step further you could legally hire a company to give your mom and dad a present of a new roof (however they could tell company not to do work or sue you if it caused them financial harm.)

The contractor needing a lien may not be warranted.  Tell your dad to speak to the crew and work out a schedule of payment that they find acceptable.  For instance he could pay for materials and pay for 1/3 labor up front and then pay incrementally.  If it is a well trusted roofing company I would then pay 1/3 the first day they show up and then 1/3 upon completion - this could be held in an escrow account or some companies will accept credit card.