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)