Q:

Should I always index all entries of a join table?

Should I always index all entries of a join table? 
I imagine that there is not much benefit to indexing both columns together, and each column should have its own index?

A:

Assuming you are talking about a many to many relationship table I normally do 
CREATE TABLE FooBar
(
FooId int NOT NULL REFERENCES Foo(FooId),
BarId int NOT NULL REFERENCES Bar(BarId),
PRIMARY KEY (FooId, BarId ),
UNIQUE (BarId, FooId )
)

On the grounds that this both ensures no duplicate rows are added and will (in SQL Server and probably all RDBMSs) implicitly create a composite index on both FooId, BarId and BarId,FooId and usually you will want to seek in either direction to either get all Bar for a Foo or vice versa. 
The two composite indexes created will cover those queries .

