evolution = variation + selection
What's happening here is likely more about selection then variation, although maybe a bit of both. I suspect this is largely the mechanics of punctuated equilibrium at work.
The way evolution is taught at high school level is typically over simplified to the point of being wrong, as indeed are many subjects. Evolution is NOT a continuous process of each generation getting better fitted to the environment via the process of natural selection acting on genetic changes introduced in individuals in that generation...
The normal way that evolution is understood to play out in practice is via "punctuated equilibrium" whereby genetic changes - which are typically too small and/or irrelevant to have any immediate impact on fitness - accumulate in animal populations over many generations. It's not the genetics of individuals that are changing so much as the genetics of the interbreeding population as a whole as accumulated changes get spread throughout the population over a number of generations. This is the "equlibrium" phase whereby genetic changes are accumulating but there is no external evidence of this as the changes are irrelevant to fitness.
What happens next is the "punctuated" part of "punctuated equilibrium" - something changes in the external environment that the animals are part of - in this case the arrival of an invasive species. These changes in the environment (drought, disease, invasive species, etc, etc) can happen very quickly compared to the speed at which genetic change accumulates. Now, it may happen that in the new changed environment some of the accumulated genetic changes that were previously benign now become a factor in fitness (either positively or negatively) and therefore a "sudden" change in the population may be seen as those individuals possessing what has now become a helpful trait, or not posessing a negative trait, prosper relative to their peers and rapidly come to dominate the population.
When a change in the environment brings about a quick change in an animal species, it is tempting - but sloppy - to say they are rapidly evolving. What happened rapidly was the change in the environment, not the slow process of genetic change that suddenly became significant.
In this case the Florida lizard population presumably already had all the traits - to some degree - that would prove positive or negative when the invading Cuban species arrived, and a quick change was seen as natural selection did it's thing and over a few generations the population became dominated by individuals having the (slowly come by) traits that now proved to be critical.
Of course there's more to how the dynamics of evolution play out than just puncuated equilibrium... While it's always going to take a long time for any complex feature such as sticky toes (or toes themselves for that matter) to evolve, the way genetic coding works is such that it may be very easy for a feature - once it exists - to be modified by a small change (e,g. a birth defect giving you unwanted extra limbs or extra sticky toes - advantageous if you mostly climb slippery trees, disadvantageous if you don't).
So.. the big picture here is that the Florida lizard species will have already accumulated the feature set that proved advantageous (or disadvantagous for those that dies giving way to the "new" variety), and this just played out once the environment changed. Subsequent to the changed environment additional variation/selection (which you could think of as optimization "tweaking") of the most critical features (toe pad size, scale stickyness) may have occurred.