I flashed Cyanogenmod to my Galaxy S3, got the stock ROM after restarting I used the Cyanogenmod installer on my phone and PC, everything went fine, and at the end received a success message. After restarting however, I was back at the stock ROM, though with all of my data and settings deleted. What did I do wrong? 

The device is rooted. I have ClockworkMod working.
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!