After some experimentation based on taylonr's link, here's what I came up with as a minimal solution for adding an iteration, in case any one else runs into this:
public void AddIteration(string projectName, string iterationName)
{
using (var tfsCollection = new TfsTeamProjectCollection(new Uri(tfsServerUrl), getTfsCredentials()))
{
tfsCollection.Authenticate();
var css = tfsCollection.GetService<ICommonStructureService>();
string rootNodePath = string.Format("\\{0}\\Iteration", projectName);
var pathRoot = css.GetNodeFromPath(rootNodePath);
css.CreateNode(iterationName, pathRoot.Uri);
}
}