That said, if you're selecting more than 5% or so of the rows in a table, you're probably better off not using an index.
Another random tip. There is a world of difference between putting indexes on 2 fields, and putting a composite index on 2 fields. If you have restrictive conditions on 2 fields, MySQL has to work with the entire list of rows that match at least one of those conditions. (I don't know whether MySQL has the trick of joining indexes together before looking at rows, but even if it does it has to work with a list of rows matching the condition.) By contrast with a composite index MySQL can only look at rows that match both conditions. Much more efficient.
http://www.slideshare.net/techdude/how-to-kill-mysql-perform...
http://forge.mysql.com/wiki/Top10SQLPerformanceTips
Good sets of additional tips/things to keep an eye out for.