In the more common cases, you get indexes on foreign keys for free. For example, using MySQL with InnoDB, declaring a FOREIGN KEY constraint will automatically create an index on the referencing table:
http://dev.mysql.com/doc/refman/5.1/en/innodb-foreign-key-co...