Una de las formas que tenes de hacerlo es hacer una función que se encarge de guardar en una variable de sesion los estados de los checkbox y otra función para asignar los estados que tenes en esa variable de sesion(podría ser variable viewstate también). Osea que en tu evento que se dispara cuando ordenas tendrías algo así:
GuardarEstadosCheck();
OrdenarGrilla();
AsignarEstadosCheck();
Donde la primera función se encarga de guardar los estados de los check en una variable de sesion.
La segunda es la función que usas vos o el bloque de codigo que usas para ordenar la grilla.
Y la tercera es una función para asignar lo que tenes en la variable de sesion a la grilla.
Esto te va a servir también seguramente si tenes que páginar o editar etc.
Para hacer la primera y la segunda función tenes un ejemplo acá:
http://aspalliance.com/774_Maintaini...ew_Control.all