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

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

As per your question to sort the product by Newest product you need to follow below steps

1. Goto Catalog->Manage Attributes->Set Product as New from Date attribute

2. Mark it as Yes for sorting in product listing page

3. Now you need to add below custom code in catalog->product->list->toolbar.phtml

   getOrderUrl('news_from_date','desc') ?>"isOrderCurrent('news_from_date') && $this->getCurrentDirection() == 'desc'): ?> selected="selected"> Newest

this option is to be inserted under Select option for Sort By