How to properly index a many-many association table?

In SQL Server, a composite index can be used for a single field search for the first column only. That means you should have an additional, one field index on FK_actor_id if there will be searches on that field without FK_Movie_id in the same query.

(although I'm not certain on whether a composite index also works for the individual columns).

Yes, it can. But only the prefix: http://use-the-index-luke.com/sql/where-clause/the-equals-operator/concatenated-keys

Also, this link adds some confusion and indicates that it might even be useful to actually specify two composite indices... one of them as (FK_movie_ID, FK_actor_ID), and the other in reverse as (FK_actor_ID, FK_movie_ID),

That's actually the thing to do.

Take one as clustering index, and the other as non-clustering index that will anyways include the clustering index key--hence no need to include the that column again (thx to JNK).

CREATE CLUSTERED INDEX a on Movies_Actors (fk_movie_id, fk_actor_id);
CREATE NONCLUSTERED INDEX b on Movies_Actors (fk_actor_id);

What is the real story?

http://Use-The-Index-Luke.com/ :)

Does a composite index automatically effectively index each column for searching on one or the other?

No. Only the prefix of the index. If you have an index (a,b,c), the query a=? and b=? can use the index. However c=? can't, nor can b=? and c=?.

Should the optimal (in read speed, not size) association table have a composite index in each direction and one on each column?

If you need to join in both directions, yes ("composite index in each direction") and no ("one on each column").

What are the behind-the-scene mechanics?

Well, same link again.

Speaking SQL Server, you might eventually also consider an indexed view. That's kind of pre-joining. Two indexes, as above, might also be fast enough.