To associate Microsoft CRM Data Records with an many-to-many relationship you have to use the AssociateRequest, but keep in mind that some entities have special request - you'll find them on the MSDN. For all standard entites you can use the example shown below.
The RelatedEntities property must be filled with a EntityReferenceCollection. That means that you can associate multiple records with one organization service call.
AssociateRequest request = new AssociateRequest
Target = contact,
Relationship = new Relationship([Relationshipname]),
RelatedEntities = entityrefcollection