How can the transaction history be checked when new addresses are generated? When a new transaction is executed via a Bitcoin-client, the sender will have a different address than the ones used in previous transactions. I also know that all the full nodes in the Bitcoin network maintain a ledger, which is basically a history off all Bitoin transactions ever made so the nodes can check the integrity of the system and the current amount of bitcoins people have available in their wallets.
How is it even possible to check all the transactions when there are constantly new addresses being generated? You can't even link a current transaction to the previous. Is there something I'm missing?
One thing you might be missing is "there are no balances".  The network doesn't know about wallets or balances, it only knows about outputs.  These outputs are either spent or unspent. Once you have this concept it's easier to understand.

If your wallet says you have a balance of 1.2345 BTC that means it "thinks" there are X number of unspent outputs that you "control" that add up to 1.2345.  It's basing this on the keys it knows about and the transactions it has seen so far. There could be 1 output with a value of 1.2345 or 100 outputs with a sum of 1.2345, or any combination.

See any transaction on blockchain.info and you'll see the inputs on the left side.  These inputs are previously unspent outputs.

https://blockchain.info/tx/ad646bbac1e44e4db199420e12fec2966903a0e078da99fab97b3156455f252a

On the right side are the new unspent outputs.  Once an output is used it's now spent and carries no balance.  Since the outputs you are using probably don't add up to exactly what you want there is a concept of change.

https://en.bitcoin.it/wiki/Change

So what about new addresses? The network doesn't need to know anything about new addresses.  When a node sees a new transaction it only has to verify the outputs being spent are not spent already i.e. they haven't been used by any other transaction (along with other verification like signature, amounts etc..)

So all transactions are linked to previous ones in that way.