You could create images of a checkbox in both states (checked and unchecked). Color them as you see fit. Use an "onclick" event to change the image to the other state and assign the appropriate corresponding value to a hidden form field.
It's not exactly the same as using a checkbox, but I'm afraid vragabond is right. If you use a standard checkbox form element, you're at the mercy of whichever O/S your visitors are using.
Good luck,
-Ron
-We are all given the same deck of cards, it's how we play the hand we are dealt which makes us who we are.