From what I know, there would be two ways to do this. Add it to the wordpress core so that all themes could take advantage of it. The admin for it would have to be incorporated into the dashboard, stuff moved around and such.
If you wanted to give the user the control through a widget or something built into the themes, the widget styling would have to be added to each theme's CSS so that it would look like it was part of the theme rather than an afterthought. Same with incorporating it into the themes itself: where to put it, design considerations so that it doesn't interfere with this or that, make it look integrated rather than tacked on, etc.
This could also be done through a plugin as is done on self-hosted blogs (much of the unique functionality here is via plugins written by the wordpress.com staff).
I know there are a couple plugins that do this for self-hoste blog and I've tested a couple but never really used them on a production site.
Still as I said, I think this functionality, being able to set a different sort order, should be added. Giving the visitor the ability to select the sort order I had not considered, but again, this might be a nice touch.