Should many to many tables have a primary key?

I agree with everything Oded said except

"It can't reasonably be used as a foreign key either."

In this case it's a pick your poison, the mapping table absolutely can be a parent, it's just a matter of the child using a multicolumn FK or not.

Take a simple case of Car and color. Each Year Auto Makers have a certain pallet of colors and each model only comes in limited number of those colors. Many - Many :: Colors to Cars models

So now design the Order table where new cars orders are stored. Clearly Color and Model will be on the Order table. If you make a FK to each of those tables, the database will permit an incorrect model/color combination to be selected. (Of course you can enforce this with code, you can't do so declaratively.) If you make the parent be the many:many table, you'll only get combinations that have been specified.

SO would you rather have a multicolumn FK and point to a PK built on both ModelID and ColorID or do you want a single column FK?

Pick your poison.

EDIT

But if it's not a parent of something, no table needs a surrogate key.

Such a surrogate key adds nothing except overhead.

Use the natural keys, make them a composite primary key if you care about duplication in this table.

To expand:

In the application, this key will be meaningless and will remain unused.

In the database, it will have no function, as you can't reasonably use it in a query for any type of meaningful result.

It can't reasonably be used as a foreign key either.

If the table tracking the many to many relationship has it's own primary key and that key is used as a foreign key anywhere else in the database then you create a dependency on that relationship. The relationship can never be removed.

For instance in the car color example, if the color for a car is ever discontinued (removed from the many to many relationship table) then any table (i.e. purchase history) referencing the primary key would be broken.