Sorry it's taken a while to respond. Your phone needs a way to determine direction (usually a magnetic field sensor, aka compass) and a way to determine down (usually an accelerometer since when the phone is not moving this will just 'feel' the pull of gravity). I think your phone has both of these:
A gyroscope will make the map smoother since it works in tandem with the compass and accelerometer to sense the change in orientation but it's not sufficient on its own (and actually, we don't use it in the currently-released version...that will change very soon).
So....am I right in thinking that you do see the map move but it's just not very accurate? Phone compasses seem to be rather unreliable things. They need frequent recalibration (which fortunately just requires you to get the phone out and wave it around a bit), some of them are very noisy (meaning the map jumps around) and some are just inaccurate (I assume lining them up on the board perfectly is not a top priority for manufacturers, but I don't know). They're also susceptible to magnetic interference (of course)...so if you have your phone in a case with a magnetic clasp then that will affect it, as might the presence of nearby electronic devices.