You can use setCell method inside of loadComplete event handle. The event loadComplete will be called after the sorted data will be loaded and after the data paging so it is a good place to change the background color of cells based on the current sort order:
loadComplete: function() {
var ids = grid.jqGrid('getDataIDs');
if (ids) {
var sortName = grid.jqGrid('getGridParam','sortname');
var sortOrder = grid.jqGrid('getGridParam','sortorder');
for (var i=0;i<ids.length;i++) {
grid.jqGrid('setCell', ids[i], sortName, '', '',
{style:(sortOrder==='asc'?'background:aqua;':
'background:yellow;')});
}
}
}
A working example which do this you can see live here.
UPDATED: Look at the modified demo also. The results seems look more nice as in the previous demo:

It shows gradient effect in all browsers excepting opera. In opera it is the same as the previous demo. In another my answer I play more with the color gradient effects.