How do nodes validate that a UTXO in a new transaction is unspent? Does it check every block in between where the UTXO first appeared and the current time to make sure it didn't get spent then? Or is there some other caching or other method to make the check faster?
Does it check every block in between where the UTXO first appeared and the current time to make sure it didn't get spent then?


Yes, but this check is not done for each UTXO individually as transactions come in, it is an ongoing process that specifies the current state of the network. 

A bitcoin node will independently work through the entire transaction history of the network, and while doing so it will build an index of unspent transaction outputs (UTXOs), which are, as the name suggests, transaction outputs which have not yet been spent, and thus are valid to be spent on the network. As new outputs are created, they are added to the UTXO set. Likewise, when a UTXO is consumed as input to a transaction, it is removed from the UTXO set. So any valid new transaction must specify one or more of these UTXOs as inputs (with the exception of coinbase transactions, which do not have any inputs).