I know that for a mining reward, a (special?) transaction is included in the the block (in the merkle tree I believe?)
Yes, the so-called coinbase transaction that sends (currently) 12.5btc to the address of the mining node/pool/etc.
But how is a transaction fee payed out exactly?
Is this also a special transaction?
I would imagine the sender of the transaction has to then also include an extra transaction to pay out the fee?
The fee is payed implicitly and it is not a special transaction. Each transaction has some inputs (addresses) and some outputs (addresses). The transaction fee is equal to: inputs value - output value. e.g. if the inputs are 1btc in total and sends to outputs a total value of 0.9995btc the remainder of 0.0005btc is payed as a transaction fee to the address specified in the coinbase transaction (miners address).