I am very confused by the term 'Contracts are immutable' does it mean when I deploy my contracts, I can't update my code again, and what actually happens when I redeploy my smart contracts after and update to the contract, do I lose all the records?
Correct, if you deploy a contract twice you will have 2 contracts that work as 2 separate entities that have nothing to do in between. If you deployed in the past one smart contract and if you decide to redeploy the same contract, because of bug fixing or smth else, then the new contract won't have the data (state) of the previous contract. You could think of solution like data transfering, but the bigger the data is the higher the cost will be. Also if your contract have conditions like for example only users can enter their data on their behalf and and you are using
msg.sender to achieve this then you cannot enter this user data on your behalf.
This is why the upgradeablity pattern is gaining more prominence. People using this pattern separate the data into state contract and the logic into proxy contract and whenever logic change need to happen proxy contract is redeployed and replaced in the state contract "firewall". You can check more about it here.