As is the case in all 50 states there is statutory and constitutional law allowing governors to issue orders, pursuant to a declared emergency. The most recent order from Florida is here. As usual, the order includes relevant citations, viz.
Article IV, Section 1 (a) of the Florida Constitution and by the
Florida Emergency Management Act, as amended, and all other applicable
The section numbers and act names differ between the 50 states, but it reduces to the same logic as was employed to mandate different degrees of shut-down and mask-wearing. The emergency powers granted to the governor are very broad, and nothing within §252.36 hints that he overstepped his authority. Such powers might (rarely) be limited under a strict scrutiny judicial review, though such reviews in the age of covid have had limited success. There is no construal of "fundamental rights" whereby a limit on what government agencies can do could be called into question.
Governments have a well-established power to regulate businesses, which this order does. The order addresses a compelling government interest (assuring the privacy of individuals, and their ability to live their lives without discrimination, etc.), and it is narrowly tailored (temperature screening is still allowed). Perhaps a business can file a lawsuit, advancing a non-obvious argument that the order infringes on the liberty of businesses, but I doubt that it would gain judicial traction.
This is not to say that the Florida legislature could not pass a mandatory vaccination law coupled with a mandate to prove one's compliance: but they have not done so. So until a law is passed by the Florida Legislature that says otherwise (and its veto is overridden), the order is just as legal as its thousands of cousins have been.