put indexes on the columns that you use in the where clause
In addition to the suggestions:
Using LIMIT clause may speed things up if you're after a specific number of records. Avoiding the '*' for return fields and naming the exact fields you want to return should also speed things up.
Using JOINS instead of subqueries where possible.