The title is misleading. "America Changes Its Mind" sounds like it's talking about people's opinions, but the data presented is about legal status at the state level. This is misleading because there's a strong discontinuity there, and the speed at which states legalize something doesn't have to be related to the speed at which opinions change.
For an extreme case, consider some issue where opinions are evenly spread out among all the states, and it very slowly changes, at a rate of, say, 0.5% per year. It would take two centuries to go from all-against to all-for at that rate, yet once you pass 50% you'd expect all the states to switch over more or less simultaneously.
The real world isn't so clean, but the same idea applies. Looking at the data, the recent examples of marijuana and same-sex marriage are changing faster, at more like 1-2%/year, but you can still see that the rate of change in state legalization is way faster than the rate of change of public opinion, as one would generally expect.
A couple of random pages with relevant poll data: