What you're looking for is something called Spline Interpolation or Approximation. There are several ways to achieve this, including Bezier curves, B-Splines, and some naive methods. I'll give a brief overview.
There are two options when it comes to creating curves: Interpolation and Approximation. Interpolation means that the curve will pass directly through the points you specify, while approximation means that the curve will just be influenced by the points you specify. Bezier curves and B-splines are both approximation curves. Both interpolation and approximation have their pros and cons, which are usually related to how the curve actually looks when it's generated (sharp turns, loops, etc).
Another method which I've actually used in an implementation before is called Catmull-Rom spline interpolation. For more information I'll direct you to this question posted on StackOverflow some time ago.
Finally, I'll leave you with a simple method of generating an approximation curve, which you may want to start with before getting into more detailed algorithms. It's called De Casteljau's Algorithm for generating Bezier curves. Given four input points or so, you could generate a longer list of points, perhaps 50, that represent points on the curve at 50 incrementally larger values of t (see the Geometric Interpretation section of that page on de Casteljau's algorithm). Then you can use your current path following algorithm on this new list of points.
EDIT: Alternatively you could have an algorithm which weights the influence of a point in the path by its distance from the object following it. In other words, as an object approaches point A, he is also getting closer to point B, the next point in the path, so some of his velocity will be towards A, and some will also be towards B. Summing these will give a total velocity which falls somewhere between the two. Since weights change with distance, this would theoretically result in a smooth curve as the object follows the path. Note that a lot of tweaking would have to be done to calculate weights to get the desired behavior.
This method is favorable to the spline interpolation I originally posted because it generates much smoother motion, whereas the spline method will suffer from the same problem you are having now, in that motion will not be perfectly smooth, but it will just be less noticeable because the objects moves on a higher resolution path.