in this file all code make as ul li tag you have to just add checkbox on before that link display it's very simple task.
For that three phtml.phtml files is use the , the path is app\design\frontend\base\default\template\catalog\layer
1)filter.phtml
2)state.phtml:
3)view.phtml
app\design\frontend\base\default\template\catalog\layer 1) filter.phtml 2) state.phtml 3) view.phtml you have to change the checkbox code in this 3 files
Make sure that this is in base folder but you have to copy this files in theme folder and do changes.