If you have a lot of users who use the report all day, but sort it differently, I'd first look at what other requirements they have that causing them to use the report differently. You may discover that the sorting is the tip of an iceberg, where several user groups are getting by with a single report, when they could use several custom built reports.
To allow them to sort and maintain their sorts through refreshes I'd go with a parameterized report through a dynamic stored procedure. There may be a simpler way out there - but this should do the trick. You will have to manually label the fields for the dynamic query source though - just ensure that the FieldSource is the same as your column name and you will pull the data correctly and be able to assign the value to cells.
Example Column sort selection:
CREATE PROC getSortColumns
AS
SELECT COLUMN_NAME
FROM INFORMATION_SCHEMA.COLUMNS
WHERE TABLE_NAME = 'DimEmployee' AND TABLE_SCHEMA='dbo'
Now create the dynamic sproc that will use the sort order:
CREATE PROC getEmployees ( @OrderByClause varchar(100) ) AS
-- Create a variable @SQLStatement
DECLARE @SQLStatement varchar(255)
-- Enter the dynamic SQL statement into the
-- variable @SQLStatement
SELECT @SQLStatement = 'SELECT Title, FirstName, LastName, HireDate, Status ' +
'FROM dbo.DimEmployee ORDER BY ' + @OrderByClause
-- Execute the SQL statement
EXEC(@SQLStatement)
You can test that the query is working manually:
exec getEmployees @OrderbyClause = LastName
In BIDS You will get warning messages that your fields are missing from the query. I tested this solution in SQL 2012, so it is possible that it wouldn't work in earlier editions, sorry I cannot confirm.
Create two data sets, one for the column names, one for your query. Setup defaults and values as normal for the column names, manually name and list the query fields on the main dataset, otherwise it will not recognize any fields in the query.
Not particularly maintainable... I'd definitely investigate the report requirements first. Hope this helps!
See 4 Guys for dynamic query explanation and this question for explanation of getting column names