A lot of discussion has appeared in this thread including a good link to CJ's article on indexing. You have a good set of responses about reasons to index or not index. I'll go "technical" on you for the purpose of providing an alternate viewpoint because you asked for guidelines on how to decide to index or not.
We do not know EXACTLY how Access builds its indexes because Microsoft has not given us any structural glimpses "inside the box." Therefore, any answer must be made in a more general context based on other similar products that have "lifted the hood" so we can see inside.
An index is conceptually a list associated with a specific table. You can have more than one index on a table and one index can include more than one field. This index is just a list of the values of the indexed field(s) and a pointer to the record having the given value(s). Where the field is marked "No Dups" then the index is a unique index and COULD be the primary key of the table, though it is not required to be. (You could have more than one candidate key.)
When you have a unique index, you can supply a value and Access will look into that index to find that value, then follow the pointer to find the right record. The speed differential comes from the idea that an index only contains two fields (unless it is a compound index). It is faster to read the two-field index than it would be to read a 50-field table.
Based on performance, we BELIEVE that a binary tree method (or something very much like that) is used to find a given value. If that is true, then the speed of the lookup will be based on the logarithm (base 2) of the number of entries in the table, rounded up.
If you have a table with 262,143 entries, the estimated number of comparisons (probes) to this table would be 18, because Log2(262,143) is just under 18. If you had no index, you would have to read (on the average) about 1/2 of the table, which would be 131K probes. Therefore, when trying to find something in the table, you would probe according to whether you had or did not have an index. And for a table that size, the difference between 18 probes and 131K probes would stand out like a sore thumb.
Another part of your question is when do you decide that you need an index? To which my best answer is, since an index is associated intimately with a table, you must know how you intend to USE the table in order to answer that question. When your table is going to be used for a LOT of lookups but it is relatively static (unchanging), you have a perfect case for an index. When the table is updated more often than used for lookups, it becomes a big question as to whether you want to bother. Because every time you update the table you have to update the index, and that can often be tricky.
The exact trade-off point is very hard to nail down. You can say that for a lookup table, an index is an easy call. For an event log table, where it is ALL update and rarely involves lookups, no index is needed. The middle ground is hard to find because it gets involved with key size and uniqueness. Shorter keys are cheaper and so favor indexing. Unique keys also favor indexing.
An earlier comment was to consider the cardinality (Colin didn't use this term). If the field is NOT unique (i.e. Dups Allowed), there is a number to consider that helps make the decision. The cardinality is the expected number (or ratio) of records returned from the table for a given value of the search key field.
Colin points out that indexing a Y/N field when you have thousands of records is a waste of space and resources. The cardinality of a Y/N field is 50% of the table (unless there is a bias in the data source). The perfect cardinality for a field to be indexed is 1 (not %), indicating that one key value returns one table value. When you are looking at cardinality values of 2-5, that isn't so bad. When the cardinality is in the thousands, you get little benefit from having an index.
When do you use indexes? When you do any of the following: Use a .FindFirst / .FindNext in a recordset. Create a JOIN between two tables using key fields. Create a query with an ORDER BY on an indexed field. Do a DLookup involving an indexed field. There are more but that should get you the idea of how often they are used.
