MS SQL creating many-to-many relation with a junction table

I would use the second junction table:

MOVIE_CATEGORY_JUNCTION
Movie_ID
Category_ID

The primary key would be the combination of both columns. You would also have a foreign key from each column to the Movie and Category table.

The junction table would look similar to this:

create table movie_category_junction
(
  movie_id int,
  category_id int,
  CONSTRAINT movie_cat_pk PRIMARY KEY (movie_id, category_id),
  CONSTRAINT FK_movie 
      FOREIGN KEY (movie_id) REFERENCES movie (movie_id),
  CONSTRAINT FK_category 
      FOREIGN KEY (category_id) REFERENCES category (category_id)
);

See SQL Fiddle with Demo.

Using these two fields as the PRIMARY KEY will prevent duplicate movie/category combinations from being added to the table.