You need to be a PSN Plus member to use the cloud storage. If you aren’t you can just save your data on a flash drive, but honestly, since you need Plus for online multiplayer and you get 2 “free” games each month, it’s worth the $50 or so per year so go ahead and ante up.
Assuming that you have PSN Plus, you need to make sure your data is uploaded to the cloud. You are offered the chance to set that up for each game when you first play it, but to make sure, go into SETTINGS > APPLICATION SAVE DATA MANAGEMENT > SAVED DATA IN SYSTEM STORAGE. Select UPLOAD TO OFFLINE STORAGE, then pick the specific game data that you want to upload to the cloud. Hit upload and you are good to go.
After you replace the HDD, just login to your PSN account, go to SETTINGS > APPLICATION SAVED DATA MANAGEMENT > SAVED DATA IN ONLINE > DOWNLOAD TO SYSTEM STORAGE. Pick what you want to download and you are all set.