How do I find what keys mysql will use for a query? I just had a query encounter a deadlock, where the lock it was trying to acquire was for an index. But when I used explain to visualize the query, I saw that a different index was listed under key and possible_key. Going back to the query, I found that the key causing the deadlock was on a column only used in the order by clause, and nowhere else in the query.

This set me thinking: Given an arbitrary SQL statement, how do I find out all of the indexes mysql is going to need to acquire a lock on in order for it to run?
You are approaching this from the wrong direction.  Any query can deadlock anytime.  So, you must be prepared to replay the entire transaction when a deadlock occurs.

Sure, it is a good idea to try to avoid deadlocks, there there are several things that can decrease their frequency.  The main technique is to make queries faster.

In the case you have mentioned, the Optimizer probably decided that avoiding the 'sort' for the ORDER BY was better than using any other index, or even using no index.  Let's see SHOW CREATE TABLE and EXPLAIN SELECT to further dissect what happened.

Another technique is to include the optimal index -- often a "composite" index over multiple columns.  Sometimes it is even good to have a "covering" index -- one that includes all the columns mentioned in the query.

When using IN, another technique is to sort the values.