There are two ways to do it

**1) Using Magento Admin Panel**

**2) Using Custom Coding**

1) To add using Magento Backend you need to follow below steps

a) Goto Catalog->Attributes->Manage Attributes

b) Select the attribute you want to add in Sort By option. Suppose you need to add a Sort By Brand Option.

c) Goto Brand Attribute and check for "Used for Sorting in Product Listing". 

d) Make it YES

Thats it you will see Brand attribute in Drop Down on product Listing page Sort by option.

2) Suppose you want to add Sort By option like Price: High-Low etc. These can't be done using attributes. For this you need to add a custom select option. Please check the link of my blog which explains how to do it 
[Universal Coder][1] 


  [1]: http://universalcoder.wordpress.com/2014/03/14/creating-custom-sort-by-in-magento/