Creating a record in Microsoft Dynamics CRM using C# is pretty straightforward. When you try to create a record together with some related records in the same request, you should use the RelatedEntities property of the parent entity (msdn).
The RelatedEntities property requires the relationship name and a collection of entities. To acquire the correct relationship name you should check your customization:
On the parent entity you have to add your related entities using the parent’s RelatedEntities property, example code:
Entity party = new Entity("contact");
party.Attributes["firstname"] = "Jonas";
EntityCollection civilstatusCollection = new EntityCollection();
Entity civilstatus = new Entity("zen_civilstatus");
civilstatus.Attributes["zen_startdate"] = DateTime.Now;
civilstatusCollection.Entities.Add(civilstatus);
party.RelatedEntities.Add(new Relationship("zen_contact_zen_civilstatus_contactid"), civilstatusCollection);
_orgService.Create(party);
Executing this request will create the parent entity (party) together with the related entity (zen_civilstatus).
Update: My plug-in trace log revealed that CRM does not handle this request very efficiently. First, the child record(s) will created without the relationship (the lookup-field remains empty)! Right after the child records will be updated to populate the lookup-field. So, first there is a create command followed by an update command. Thus we should avoid the use of RelatedEntities to create related records!