The Full Faith and Credit clause says
Full faith and credit ought to be given in each state to the public
acts, records, and judicial proceedings, of every other state; and the
legislature shall, by general laws, prescribe the manner in which such
acts, records, and proceedings, shall be proved, and the effect which
judgments, obtained in one state, shall have in another
For example, if Jones has been found liable to Smith in California, according to this clause, Nevada must "believe" this finding of California, and cannot say "Jones has not been found liable to Smith". Likewise Arizona has to recognize the validity of court records from Tennessee, etc. Congress then passed a law, the source of 28 USC 1738, which says
The Acts of the legislature of any State, Territory, or Possession of
the United States, or copies thereof, shall be authenticated by
affixing the seal of such State, Territory or Possession thereto.
The records and judicial proceedings of any court of any such State,
Territory or Possession, or copies thereof, shall be proved or
admitted in other courts within the United States and its Territories
and Possessions by the attestation of the clerk and seal of the court
annexed, if a seal exists, together with a certificate of a judge of
the court that the said attestation is in proper form.
Such Acts, records and judicial proceedings or copies thereof, so
authenticated, shall have the same full faith and credit in every
court within the United States and its Territories and Possessions as
they have by law or usage in the courts of such State, Territory or
Possession from which they are taken.
Other laws such as 42 USC Ch 136 known in part as The Violence Against Women Act of 1994
and 28 USC 1738B ("Full faith and credit for child support orders") were passed which take away state power to say "that's not our law". In the case of marriage (which was subject to state-specific recognition exceptions until US v. Windsor, 570 U.S. 744 fixed that) interstate recognition of marriage derives from the Equal Protection Clause – marriage is a fundamental right. Driving and fishing are not fundamental rights. The reason why driving licenses are recognized across states is that every state has a clause to that effect in their laws (for politically-sensible reasons). The reason why fishing licenses are not ?ever recognized across state lines is that it's not necessary, legally or politically, to do so. Even in states with teaching certification reciprocity, you still have to apply for a new license when you start teaching in another state.
In other words, the Full Faith and Credit Clause does not say "permission granted by one state shall be binding on all states".