I overshot the waypoint). It seemed to pick this up and told me to turn left instead of right.

That's his intent, yes.

My problem is that it sometimes tells me the wrong turning direction, even when I'm still on course and I haven't overshot a waypoint.

Now my question is how does it know this? Does it get your bearing from some GPS data?

Yes. It uses the same information as it does to display your directional arrow on the GPSapp screen. It can see you are traveling "north" for example, because it sees your position from moment to moment.

It can't REALLY tell which direction your car is facing. But it can make a pretty darn good guess, based on the last few location samples.