You need to create a single index which contains all the columns which you are in your WHERE clause as well as your ORDER BY clause. The columns in your SELECT statement should be put into the index as included columns (if using SQL 2005 or higher).
You will probably end up with a few different indexes to handle all your queries. Each query with a different ORDER BY Clause will need it’s own index, with the Order by columns included in the index in the order you are sorting by them. The queries which don’t have ORDER BY statements can all be handled by one index just make sure that you have all the columns that all the queries return listed in the INCLUDE section.
Look at the execution plan to see what index is currently being used.