Determining the fee of a transaction is actually very easy.
As you know, a transaction has inputs and outputs, where each output has an associated amount and a script, and each input is a link to an output of a previous transaction, along with whatever data is needed to satisfy the previous output's script.
A transaction fee is implemented by simply having the total value of the outputs be less than the total value of the inputs. The difference represents the transaction fee and can be added to the block's coinbase transaction, to be collected as part of the miner's reward.
So in order to calculate the fee of a transaction, the miner simply has to:
Sum up the values of the outputs of the transaction.
For the inputs of the transaction, find the associated previous outputs and sum up their values. (These will normally have already been stored in an indexed database, so it's easy to find them.) This gives the total input value.
Of course, the miner also has to check that the transaction is valid, since any block containing an invalid transaction is itself invalid, and won't be included in the block chain. This is a little harder, because it does require actually "decoding" and executing the script for each of the previous outputs, and verifying that the input data and signatures provided in the current transaction satisfy those scripts. But by design, the instructions available for those scripts is quite limited (for instance, there are no loops). So this verification is of bounded complexity, and it can't be too hard in a computational sense. Of course, the code to actually do the verification is already implemented in Bitcoin Core, so in practice all the miner has to do is run it.