You need to calibrate the sensors! Go to the Google Play Store and download an app called GPS Status. Go into it and then press the Menu button and choose Tools. Then select Compass Calibration. After selecting that you then need to rotate the phone twice through each axis. I hold the phone vertically and rotate it twice around (spin the phone from screen facing you all the way around till you see the screen and do it once more). I then rotate it by spinning the phone so that (while the screen is facing you) you rotate it so that it goes completely upside down and back to right side up. Then you spin it, and this is the hardest so be careful you don't drop it, upside down to rightside up going away from you. So you hold the phone with the screen facing you then the bottom goes away from you with the top going toward you, it goes around a full 360 as all the others.
This is probably confusing as hell but just try to understand it needs to be rotated twice along each of the 3 axis'. Once you do this the phone will be 100% in sync with your location *and* the direction which you are facing.
Keep in mind, the GPS goes out of sync often and needs recalibrating! It's not the Galaxy S3, my Droid 2 also went out of sync often. Some people when calibrating hold their phone and swing it in a figure 8 pattern, though I've not tried that it would certainly be easier.
Rev.