So far I've reordered my plugin's records according to the documentation, but now I need to take it a step further.
Let's say I have products which have multiple categories:

apple  -> (fruits, desserts)    
banana -> (fruits, desserts)
cherry -> (fruits, desserts)

Now the idea is to reorder the products according to each category:

fruits:
1 - apple
2 - banana
3 - cherry

desserts:
1 - cherry
2 - apple
3 - banana

I guess I need an extra pivot table reorder_category_product but, that aside, how can I achieve that ?

You may be able to do this by using a custom Pivot Model (you can specify this in your $belongsToMany() relation using "pivotModel => YourModel" .

This Pivot Model should use the Sortable trait and have an extra "sort_order" field in its table.

If I understand you correctly I should create a pivot model called for instance "Order" using the Sortable trait and having an extra "sort_order" field. Then adding a $belongsToMany("order => MyModel") relationship in both my Product and Category models.
To get the products ordered by category I guess the pivot model table should look something like this:

category_id | product_id | sort_order 
      1            1            1
      1            2            2
      1            3            3
      2            3            1
      2            1            2
      2            2            3

Obviously, I'd like to reorder my products from the product list through the "Reorder" button.
I probably have to override some reordering methods to tell October to use the pivot model instead of the product model.
But what are these methods and what should I modify ?