Order by column should have index or not?
Yes, MySQL can use an index on the columns in the ORDER BY (under certain conditions).  However, MySQL cannot use an index for mixed ASC,DESC order by (SELECT * FROM foo ORDER BY bar ASC, pants DESC).  Sharing your query and CREATE TABLE statement would help us answer your question more specifically.

For hints on how to optimize ORDER BY clauses:
http://dev.mysql.com/doc/refman/5.1/en/order-by-optimization.html

Edit 2012-01-21 8:53AM

There were questions about the source of my statement about using an index with mixed ASC/DESC 
in the ORDER BY.  From the ORDER BY Optimization documentation:


  In some cases, MySQL cannot use indexes to resolve the ORDER BY,
  although it still uses indexes to find the rows that match the WHERE
  clause. These cases include the following:
  
  ...
  
  You mix ASC and DESC:
  
  SELECT * FROM t1 ORDER BY key_part1 DESC, key_part2 ASC;
  
  ...


Also, the DESC keyword is meaningless in CREATE INDEX


  An index_col_name specification can end with ASC or DESC. These
  keywords are permitted for future extensions for specifying ascending
  or descending index value storage. Currently, they are parsed but
  ignored; index values are always stored in ascending order.