Las claves foráneas las puedes usar en tablas de tipo:
InnoDB
No MyISAM como es el tipo de tabla por defecto .. Las puedes usar desde: Mysql versión 3.23.43b en adelante .. En tablas MyISAM o versiones inferiores, las claves foráneas Mysql no respeta la integridad referencial de los datos .. así q es taréa de tu programación q gestione esas tablas el que la respete.
http://www.mysql.com/doc/en/InnoDB.html
Si mal no recuerdo .. para Mysql 4.1.x en adelante las tablas tipo MyISAM van a soportar claves foráneas .. Pero de momento para la versión estable de Mysql última solo las tablas InnoDB
Puedes ver los "change history" de todas las versiones pasadas y futuras de Mysql en: (por ahí ronda Mysql 5 0_0 )
http://www.mysql.com/doc/en/News.html
Un saludo,