I had similar problem when I first tried installing a custom ROM (CyanogenMod ofcourse) on my ZTE Blade phone. Everytime I tried to install the custom ROM and getting the success message, it asked me to restart the phone but after restarting it again turn back to the stock ROM. I researched a lot and found a pretty simpler solution; I rooted my device using z4root app and then installed Custom Recovery (Clockworkmod Recovery) on it (this custom recovery is device specific many a times, so first ensure if Clockworkmod Recovery is compatible with your Galaxy S3) Now after your phone get rooted and have a custom ROM installed, you will be able to install your custom ROM on it by booting into the recovery.
Feel free to ask me futher if you find difficulty at any point and I will be happy to elaborate the steps further. Cheers!