UPDATE:
The below answer references the state of things before widespread availability of CSS3. In modern browsers (including Internet Explorer 9 and later) it is more straightforward to create checkbox replacements with your preferred styling, without using javascript.
Here are some useful links:
It is worth noting that the fundamental issue has not changed. You still can't apply styles (borders, etc.) directly to the checkbox element and have those styles affect the display of the HTML checkbox. What has changed, however, is that it's now possible to hide the actual checkbox and replace it with a styled element of your own, using nothing but CSS. In particular, because CSS now has a widely supported :checked
selector, you can make your replacement correctly reflect the checked status of the box.
OLDER ANSWER
Here's a useful article about styling checkboxes. Basically what that writer found was that it varies tremendously from browser to browser, and that many browsers always display the default checkbox no matter how you style it. So there really isn't an easy way.
It's not hard to imagine a workaround where you would use javascript to overlay an image on the checkbox and have clicks on that image cause the real checkbox to be checked. Users without javascript would see the default checkbox.
Edited to add: here's a nice script that does this for you; it hides the real checkbox element, replaces it with a styled span, and redirects the click events.