The use of integers, as suggested by Andre may be your best bet, but I’d test it. It may only work for the geekier of users.
I, however, would like to suggest that your second option of having dedicated sorting controls is often worth the clutter. This is especially true if the sorting controls are interactive; for example, users can open a dropdown for each criterion to change ascending/descending or change it to a different field, and there are + and x controls to insert or delete a criterion (users can still click on column headings too, but that’s more an expert shortcut).
First of all consider that if you need to support multi-order sorting, then you probably have a long table with multiple columns –you’re probably displaying 20 or more rows and have five or more columns. In this context, the relative amount of clutter of dedicated sorting controls is fairly minor.
Secondly, the sorting controls only need to show criteria up to the identifier field (e.g., name) or a timestamp field or other field that has practically unique values for each row. There’s no point in cluttering the display beyond that, because it doesn’t functionally affect the order. In most applications, time or identifier is often the first or second criteria, so usually you’re showing only one or two fields, so it’s not much clutter.
Then there’re the advantages of dedicated sorting controls:
The users only have to look in one place to see the sort order, rather than scan across all the columns and mentally assemble the order from integers. The latter can be awkward if you have so many fields that the table scrolls horizontally.
The sorting functionality has better discoverability. The “sorting” label makes it clear the user can sort, and the “+” controls indicate that the user can have multi-order sorts.
The same kind of sorting controls can be used for items in non-column layout, such as when each item is a "page," or you have items laid out like Stack Exchange UX questions. You can have a consistent means of sorting across your application or suite.
Users can more easily edit the sorting order, for example, changing the second criterion to descending without making it the first criterion. Changing the sort order with the column headers usually means starting over from scratch.
User can create multi-order sorts in an intuitive sequence from higher to lower order criteria. Using column headers requires users think backwards.
You can include “canned” multi-sort orders that users commonly use. For example, one option on the sort control dropdown can be “Probability then Impact” to allow users to sort on the two fields at once with one input.
You can sort on attributes that are not shown. This could be attributes whose exact values have little meaning to users, but are still useful for sorting, such as relevance scores for search results.
Oh, and BTW, those ascending/descending arrows everyone uses? They don't work.