You should be able to do something like this:

SELECT *
FROM
    TableName
WHERE
    (Forename LIKE '%' + @SearchValue + '%') OR
    (Surname LIKE '%' + @SearchValue + '%') OR
    (@SearchValue = 'ALL')
ORDER BY 
    CASE @OrderByColumn
    WHEN 1 THEN Forename
    WHEN 2 THEN Surname
    END;

• Assign 1 to @OrderByColumn to sort on Forename .
• Assign 2 to sort on Surname .
• Etc... you can expand this scheme to arbitrary number of columns.

Be careful about performance though. These kinds of constructs may interfere with query optimizer's ability to find an optimal execution plan. For example, even if Forename is covered by index, query may still require the full sort instead of just traversing the index in order.

If that is the case, and you can't live with the performance implications, it may be necessary to have a separate version of the query for each possible sort order, complicating things considerably client-side.

The accepted answer does not work if columns are of different types. You get a "Conversion failed when converting date and/or time from character string." for instance.

I've used a double-CASE (or triple or whatever) solution, each CASE accepting the same type of data, filling with NULL values the others.

I know, it's ugly, and certainly not performant ^^

ORDER BY
    CASE -- process CASE for VARCHAR
        WHEN @OrderByColumn = 1 THEN Forename
        WHEN @OrderByColumn = 2 THEN Surname
        ELSE NULL
    END,
    CASE -- process CASE for DATETIME
        WHEN @OrderByColumn= 3 THEN BirthDate
        ELSE NULL 
    END