Indexing means building a seperate set of information about the records.
In effect you are building an "abbreviated" copy of your tables.
This copy is used to find which records you want without having to read the whole table.
You can probably imagine that if you use small tables or small columns, the index can be just about the same size as the original table, and thus just as slow.
At that point, reading the index can take just as much time as reading the real table, so everything can actually slow down.
Another time when indexes are not really usefull is when your query returns most of the records in the table.
In that case, the engine still has to read most of the real table to get the data, so the speed of finding the records is not a big advantage (the point of the index was to prevent the engine from having to read all records)
There is a nice article about this in the articles section.