The RhinoDoc.Materials table is indeed a bit of a pain to use. When you add one material, then add it to five objects you’ll have RhinoDoc.Materials with five entries. The water gets indeed muddied when you start deleting materials as well… As you noticed the material shows up in the Materials editor only once it is actually assigned to some object or layer.
Indeed the RhinoDoc.RenderMaterials is as @nathancoatney found: once you add a RenderMaterial to the document it shows up in the Materials editor. And adding it to 5 objects results in RhinoDoc.RenderMaterials have still only the one instance.
The old-style materials have a RenderMaterial version - so the five objects of the first paragraph all reference just one RenderMaterial, but you see five different material indices into RhinoDoc.Materials.
If you find it easier to create an old-style material you can still do that, just create a RenderMaterial from it before you add it to the document.
The below code is pretty much what @nathancoatney has, and is also pretty much what the sample code does that I linked to.
oldmat = Rhino.DocObjects.Material()
oldmat.DiffuseColor = the_color_you_want
oldmat.Name = "the material"
newstylemat = Rhino.Render.RenderMaterial.CreateBasicMaterial(oldmat)
sc.doc.RenderMaterials.Add(newstylemat)
yourob = GetYourRhinoObjectFromDoc()
yourob.Attributes.MaterialSource = Rhino.DocObjects.ObjectMaterialSource.MaterialFromObject
yourob.RenderMaterial = newstylemat
yourob.CommitChanges()