Given an arbitary polygon with vertices stored in either clockwise/counterclockwise fashion (depicted as a black rectangle in the diagram), I need to be able to subtract an arbitrary number of circles (in red on the diagram) from that polygon. Removing a circle could possibly split the polygon into two seperate polygons (as depicted by the second line in the diagram).
I'm not sure where to start.
Warning: getting code to do this absolutely right is tricky. (Conceptually it's fine, but you can quickly get bogged down in numerical errors and edge cases.) You're basically asking for a 2D version of Constructive Solid Geometry. You might want to see if you can use an existing library written by an expert in computational geometry. There are some libraries here that will probably do what you want, but you'll have to choose a representation that suits you best and convert what you have into that representation.
Here's a freeware polygon clipping library (written in Delphi and C++) that does what you're asking: http://sourceforge.net/projects/polyclipping/