Some example:

                    var relation1 = new CategoryProductRelation();

                    relation1.Product = product;

                    relation1.Category = category1;

    var relation2 = new CategoryProductRelation();

                    relation2.Product = product;

                    relation2.Category = category2;

  product.CategoryProductRelation.Add(realation1);

  product.CategoryProductRelation.Add(realation2);

 product.Save();

After that only relation1 is in db.

Which version are you on?

2.6.1.0

Try

category1.AddProduct(product, 0);
category2.AddProduct(product, 0);
category1.Save();
category2.Save(); 

is working on a reply...