How do I add indexes to MySQL tables?

I've got a very large MySQL table with about 150,000 rows of data. Currently, when I try and run

SELECT * FROM table WHERE id = '1';

the code runs fine as the ID field is the primary index. However, for a recent development in the project, I have to search the database by another field. For example:

SELECT * FROM table WHERE product_id = '1';

This field was not previously indexed; however, I've added one, so mysql now indexes the field, but when I try to run the above query, it runs very slowly. An EXPLAIN query reveals that there is no index for the product_id field when I've already added one, and as a result the query takes any where from 20 minutes to 30 minutes to return a single row.

My full EXPLAIN results are:

| id | select_type | table | type | possible_keys| key  | key_len | ref  | rows  | Extra       |
+----+-------------+-------+------+--------------+------+---------+------+-------+------------------+
|  1 | SIMPLE      | table | ALL  | NULL         | NULL | NULL    | NULL |157211 | Using where |
+----+-------------+-------+------+--------------+------+---------+------+-------+------------------+

It might be helpful to note that I've just taken a look, and ID field is stored as INT whereas the PRODUCT_ID field is stored as VARCHAR. Could this be the source of the problem?

ALTER TABLE `table` ADD INDEX `product_id_index` (`product_id`)

Never compare integer to strings in MySQL. If id is int, remove the quotes.

ALTER TABLE TABLE_NAME ADD INDEX (COLUMN_NAME);

You can use this syntax to add an index and control the kind of index (HASH or BTREE).

create index your_index_name on your_table_name(your_column_name) using HASH;

or

create index your_index_name on your_table_name(your_column_name) using BTREE;

You can learn about differences between BTREE and HASH indexes here: http://dev.mysql.com/doc/refman/5.5/en/index-btree-hash.html