Rarely do I call down my friend Banana, but here I must clarify:
a) Checking that all columns in a join, where, order by clauses are all indexed
Not all columns in a WHERE are appropriate for indexing. When the number of rows returned as part of the SELECT include a selected value for something like GENDER, where you expect about 50% of the rows to be selected by such an index, you gain very little. I agree with the JOIN and ORDER BY suggestion.
b) Verifying that the queries are optimized
c) Ask for few as possible records from any forms; always write queries with a WHERE condition as a recordsource for form and never use tables.
The first sentence in C and my caveat to A both refer to something called "cardinality" - the number of rows expected from a query. For a query of a single value against a unique index, cardinality is 1. For the Male/Female case mentioned earlier, cardinality is about 50% of the population of the table. To really optimize your queries, try to specify the fields with lowest cardinality first.
The reason this is important is that Access imposes a limit on the number of indexes you can have, and each index costs you more overhead if you do lots of updating of indexed fields or if you do lots of insertions. So you want to minimize the number of indexes and maximize them at the same time. Which usually means you must strike a happy medium. (Why you should assault a joyous fortune-teller, I'll never know... but that's the phrase they use.)
Seriously, it is a fine art to tune indexes for optimum speed in a complex system. You will probably have to tinker with it.