Some Florida conservatives want to recall Senator Marco Rubio because of his support for a proposed immigration law. Florida currently lacks a recall mechanism for United States senators in its law, so a law would need to be enacted. But can Florida enact such a law?

Probably not. 

The major case in this area is Committee to Recall Robert Menendez from the Office of U.S. Senator v. Wells  in New Jersey in 2010.  The New Jersey Supreme Court concluded by a 4-2 margin that a recall was an additional qualification to the office of a United State senator, and, as additional qualifications are prohibited, the recall mechanism must fail.

While the New Jersey Supreme Court has not been a model of fidelity to legal texts in the election law context, it relies primarily on the broad pronouncements from the United States Supreme Court in Powell v. McCormack  (refusal to seat a member for his involvement in a scandal) and U.S. Term Limits v. Thornton  (refusal to list a candidate for office after the candidate met a term limit). It's possible that the Court might view those cases as different in kind from a recall mechanism after an individual has been elected and seated (there were, after all, dissenting justices in U.S. Term Limits ), but there's no guarantee.

Regardless, there's also the prior question of whether a recall could even appear on the ballot. Some state judiciaries reserve judgment on the constitutionality of ballot initiatives (in this case, it would be a recall mechanism) until after it passes: it's an element of judicial restraint, as the political process may work itself out and render the need for judicial involvement moot; and it allows an expression of democracy to occur at the polling place even if the matter is unconstitutional. But other state judiciaries recognize the cost and political uncertainty of such matters and allow for a prior adjudication.

Florida tends to have a middle ground on this issue:

If a proposed amendment to the state Constitution by its terms specifically and necessarily violates a command or limitation of the Federal Constitution, a ministerial duty of an administrative officer, that is a part of the prescribed legal procedure for submitting such proposed amendment  to the electorate of the state for adoption or rejection, may be enjoined at the suit of proper parties in order to avoid the expense of submission, when the amendment, if adopted, would palpably violate the paramount law and would inevitably be futile and nugatory and incapable of being made operative under any conditions or circumstances. But if a duly proposed amendment to the Constitution may, if adopted, conceivably be valid in part or as applied to some conditions, its submission to the voters should not be enjoined, because in such a case the State has a right to the submission and, if it is adopted, to the operation of the amendment as far as it may legally be made effective. 

If it is not clearly shown that by its terms the proposed amendment to the state Constitution, as an entirety, expressly and specifically violates some command or limitation of the Federal Constitution so as to render it wholly void, or that the proposed amendment is otherwise wholly incapable of operation, its submission to the electorate of the state for adoption or rejection as required by the Constitution should not be enjoined. even though, if adopted, it may in appropriate procedure by proper parties, allegations of facts, and proof or admissions, be shown that the amendment violates paramount federal law and is therefore inoperative to the extent that it is duly shown to be invalid. 

Gray v. Winthrop, 156 So. 270, 272 (Fla. 1934).

In short, Florida cours refused to enjoin ballot measures that are not invalid in their entirety; but if the measure would "necessarily violate[]" the federal Constitution, it would enjoin it.

That means that if the recall mechanism is unconstitutional (and it may be), a Florida court may enjoin it from appearing on the ballot. While other states may allow voters to recall a senator, then invalidate the recall after the election, it seems like that Florida would act before the election.

Of course, the Florida courts may reach a different conclusion than the New Jersey courts and find the recall constitutional, which would set up a case before the United States Supreme Court. 

But for supporters of a recall mechanism who want to get Florida to enact such a law in the first place, it's useful to recognize the substantial likelihood that even a successful recall effort would find trouble ahead.