How to change sorting options display name in magento?

To change sorting options display name as well as any other extension texts when using the Improved Sorting please open the file app\locale\en_US\Amasty_Sorting.csv

Add, for example line,

"New", "New In"

and refresh the cache.

To change the default wording (price, brand) you may use

1) app\locale\en_US\Mage_Catalog.csv will change all occurrences, not sure it's applicable in that case

2) open admin > catalog > attributes > manage attributes > and set appropriate store labels

3) use inline translation tool (not recommended, as it will be hard to find the translation when you need to change it)