I have covered inserting a record using the Add() methid in the article "Add Case Example using Web Service Interface". Below is some example code that shows how to insert a record using the AddRecord() method of the SOAP webservices.

WebService CRM71 = new WebService();
logonresult CRMLogon = CRM71.logon("Admin", "");
CRM71.SessionHeaderValue = new SessionHeader();
CRM71.SessionHeaderValue.sessionId = CRMLogon.sessionid;

crmrecord[] oppoList = new crmrecord[1];

crmrecord aNewOppo = new crmrecord();
aNewOppo.entityname = "opportunity";
aNewOppo.records = new recordfield[4];

recordfield aForeignKeyField = new recordfield();
aForeignKeyField.name = "primarycompanyid";
aForeignKeyField.value = 30;
aForeignKeyField.type = crmrecordtype.integer;
aForeignKeyField.typeSpecified = true;

recordfield aDescriptionField = new recordfield();
aDescriptionField.name = "description";
aDescriptionField.value = "test oppo";
aDescriptionField.type = crmrecordtype.@string;
aDescriptionField.typeSpecified = true;

recordfield aStatusField = new recordfield();
aStatusField.name = "status";
aStatusField.value = "In Progress";
aStatusField.type = crmrecordtype.@string;
aStatusField.typeSpecified = true;

recordfield aStageField = new recordfield();
aStageField.name = "stage";
aStageField.value = "Lead";
aStageField.type = crmrecordtype.@string;
aStageField.typeSpecified = true;

aNewOppo.records[0] = aForeignKeyField;
aNewOppo.records[1] = aDescriptionField;
aNewOppo.records[2] = aStatusField;
aNewOppo.records[3] = aStageField;

oppoList[0] = aNewOppo;
addresult aResult = CRM71.addrecord("opportunity", oppoList);
 
CRMsp1.logoff(CRM71.SessionHeaderValue.sessionId);

Notes:

1. This will create an opportunity for the company with the ID 30, which in the demo data is Design Right.
2. This has not included all of the fields. E.g. The assigned user (oppo_assigneduserid) is not populated.