For a complex query, SQL Server may decide that it needs to sort portions of data in your query, and may even require multiple sort operators based on which indexes are available and the complexity of your query.
These sorts can definitely impact the performance of your query especially if you are working with large tables, and in some cases you'll find that adding an Order By statement will significantly change the execution plan SQL Server generates for your query.
If you're interested in seeing the impact of Sorting the queries you're tuning, run the Actual Plan with SQL Sentry Plan Explorer (free) or using SSMS with "Include Actual Execution Plan" turned on and look at the Ordered Indicator by hovering over the individual data steps in the plan. In Plan Explorer you can also look at the Ordered column in the Plan Tree or Top Operations view.
For something as simple as:
Order by PrimaryKey
You should find that while the Order By doesn't seem to change the query plan of your query, that the Ordered indicator in the execution plan does change from False to True when you add the Order By.
You'll may have heard that "the order of the results returned from a SELECT statement cannot be guaranteed without an ORDER BY clause"; One reason for this is a feature of the Enterprise Edition of SQL Server that allows SQL Server to piggyback one table scan on top of another, sometimes called a "Merry-go-round" scan and also called "Advanced Scanning".
For further research, I highly recommend both of the following books which are currently available as free ebooks from RedGate:
Hope this helps!