Admin > system > config > catalog > product listing by holds the default sort order field.

To sort differently by category, Go to admin > catalog> manage categories and click on a category. Under the display settings tab you will see: Default Product Listing Sort By

You can adjust this to the sort by field you want. By default it’s set to Best Value. Best Value means the order that you have set under the Manage Products in the Edit Category Page as shown by the arrows in the screenshot below:

If you don’t enter sort orders, then the products order will change everytime the category page is refreshed.