I'd follow the advice of SW4's answer – to hide the checkbox and to cover it with a custom span, suggesting this HTML:

I'd follow the advice of SW4's answer. Not anymore: Volomike's answer is far superior to all the answers here (note my suggested improvement in the comment to the answer). Proceed reading this answer if you are curious about alternative approaches, which this answer comments.

First of all, hide the checkbox and to cover it with a custom span, suggesting this HTML:

Do not hide it using visibility: hidden or display: none

Test it on JS Fiddle

Do not hide it using visibility: hidden or display: none

Test it on JS Fiddle

#Do not hide it using visibility: hidden or display: none

5. Add focus outline

    input[type="checkbox"]:focus + span:before { outline: 1px dotted #aaa; } 

   Safari doesn't provide this feature (see @Jason Sankey's comment), you should use window.navigator to detect the browser and skip it if it is Safari.

6. Set gray color for disabled checkbox

    input[type="checkbox"]:disabled + span { color: #999; } 

7. Set hover shadow on non-disabled checkbox

    input[type="checkbox"]:not(:disabled) + span:hover:before { text-shadow: 0 1px 2px #77F; } 

#Demo Fiddle

Do not hide it using visibility: hidden or display: none

5. Add focus outline

    input[type="checkbox"]:focus + span:before { outline: 1px dotted #aaa; } 

   Safari doesn't provide this feature (see @Jason Sankey's comment), see this answer for Safari-only CSS

6. Set gray color for disabled checkbox

    input[type="checkbox"]:disabled + span { color: #999; } 

7. Set hover shadow on non-disabled checkbox

    input[type="checkbox"]:not(:disabled) + span:hover:before { text-shadow: 0 1px 2px #77F; } 

Test it on JS Fiddle