Specifically to your confusion with Scalia's statement, Scalia's belief is that if the Founding Fathers wanted to say "Capital Punishment should be unconstitutional" they had ample space to say that in the Constitution. They were well aware of it and did not have a problem with it. Additionally, Originalism doesn't just look at the text of the constitution, but other historical sources to provide insight into the drafting in the minds of the people who wrote the constitution. Such documents include the Federalist Papers (which went into depth about the meaning of each article and it's limits) the Anti-Federalist Papers (A critique that pointed out flaws in the unamend Constitution and lead to the creation of the Bill of Rights Amendments), and other writings by the framers where they talk at length about what they meant when they wrote the thing (A universal trick to get any writer to talk to you is ask them about their works... getting to shut up is now the hard part.).
As it follows, not only is there no mention of Capital Punishment in the Constitution and it was a form of punishment common to the time, and likely there were some communication on the subject in other matters, there is likely a historical record that leads to the conclusion that it is not "cruel and unusual". A textualist look would point out that "unusual" means if it's not a usual punishment for the crime and it is cruel, it is unconstitutional. But what's more important is the word "and" because it allows for a punishment that is not cruel but is "unusual" (A judge making juvenile offenders hold up signs identifying the crime they committed in lieu of sending them to Juvvie is unusual, but hardly cruel compared to involving juvenile corrections) or if the punishment is cruel but quite common (capital punishment) it's okay to be constitutional. The preceeding clause about excessive fines and bail also limits the application as Capital Punishment might be acceptable for those who commit pre-meditated murder, but no pro-Capitol Punishment advocate will debate that it's use for Jay Walking is beyond excessive, if not cruel and unusual.
Historical context standards aren't just used here as the latest ruling on gun control laws requires the state to show that restrictions must have historical basis for enacting (i.e. you have to show that the restriction of a certain gun or gun accessory has a similar historical precedence.).
And that isn't to say the definition of "cruel and unusual" cannot change over time. While a staple sight in Colonial period pieces, the use of the pillory was largely abolished in the United States in 1826 to relatively little fanfare (and certainly well before it rose to SCOTUS making a decision on it.). The nature of what is considered "Fighting Words" is defined more by the courts by what it is not than what it is (suffice to say, aside from the case that introduced the term, every case involving Fighting Word Doctrine has been ruled to not be an example of the doctrine). And the protections provided by the Third Amendment were against intrusion so beyond the pale of the people that to this day no SCOTUS case has decided an issue related to the 3rd Amendment (Quartering of Soldiers if you didn't know).
Proponents of Originalism take the state of the world at the time it was written and what the common usage of the word was. The logic to assume otherwise is like saying that one should read the line of Hamlet "Get Thee to a Nunnery" as Hamlet telling Ophelia to join a convent... when his usage and intent track much more with the fact that when it was written, "Nunnery" was slang for "Whore House". Or for a more recent one, that Fred Flinstones and Barney Rubble were actually lovers with Wilma and Betty being their respected Beards... because when your with the Flinestones, you'll have a gay ol' time. Just because the way a word is used changed, does not diminish that it's common usage in the contemporary time changes.
