Простейший вариант такой:
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>Untitled Document</title>
</head>
<body>
<style type="text/css">
label {
position: relative;
overflow: hidden;
padding-left: 21px;
background: url(http://javascript.ru/forum/attachments/dom-window/317d1268037500-svojj-stil-dlya-checkbox-checkbox-gif) no-repeat;
}
label:hover {
background-position: 0 -23px;
}
label.checked {
background-position: 0 -46px;
}
label.checked:hover {
background-position: 0 -69px;
background-color: #fec;
}
label input {
position: absolute;
left: -9999px;
}
</style>
<label><input type="checkbox" /> checkbox</label>
<script type="text/javascript">
var label = document.getElementsByTagName("label")[0];
var input = label.getElementsByTagName("input")[0];
input.onclick = function () {
label.className = input.checked ? "checked" : "";
};
</script>
</body>
</html>
Замечания: не хватает картинок для состояния input:focus, картинка для input:checked:hover ничем не отличается от input:checked (поэтому добавил изменение цвета фона).
input можно не сдвигать, а накрыть изображением или вытолкнуть в невидимую область изображением, чтобы при отключенных картинках input можно было найти.
Фон можно менять у какого-нибудь вложенного span, чтобы пользователь мог увеличивать только размер шрифта, а не масштаб всей страницы.
В общем, переделывать инпуты — дело муторное и неблагодарное. Дизайнеру по голове за это.