I'm new to bitcoins and I was wondering; if I generate an address, add money to it (from MtGox for example), remove the address and use another address in the future. Would it be possible to link those two addresses together?
Or would I be perfectly safe (anonymous)?
You will not be anonymous unless you take special measures to make it so.
If you simply not use the old address to receive new payments, in all likelihood there will be a point where the client will combine outputs from this address and your new addresses, and this will indicate that the addresses belong to the same person.
It will be somewhat better if you send all the coins from the old address to a new one (with change, so the amount you should send is lower than the total). Then everyone will know that coins moved from the old address to the new one, but they can't tell if they both belong to you or if this was a payment to another party.
Bitcoins are tied to a specific address, it is not possible to link addresses together. You can send coins from one address to another, provided you have the private key for the first one. If you lose the private key, those coins are lost, they effectively can't be recovered, ever.