http://jsbin.com/rahuq/1/
input[type=checkbox]:checked{
outline: 2px solid red;
}
Tested in Android 2.3 and 4.3 and worked pretty well :)
If you really want to style it you can do like:
http://jsbin.com/mikul/1/
<input id="ch1" type="checkbox"><label for="ch1"></label>
input[id^=ch]{
display:none;
}
input[id^=ch] + label{
display:inline-block;
width:16px;
height:16px;
background:green;
border-radius:50%;
}
input[id^=ch]:checked + label{
background: red;
}
Also tested in Android 2.3 and 4.3
Also tested in Firefox Mobile browser and works
Also tested in Chrome Mobile and native browsers
Upload by Roko

Edit by @what:
Here's a screenshot from Firefox for Android that shows that this does not work in that browser:
Upload by @what