Si lo que quieres es simplemente modificar iconos es bastante facil, eso si requiere de tiempo, paciencia y probar una tras otra vez como van quedando todo. Puede que algo sea muy bonito pero luego en pantalla junto el resto, colores, etc... quede horrible o que de algun problema por no tener el la imagen el tamaño correcto (puede quedar pequeño, o muy grande solapandose con alguna letra, a las malas el sistema lo redimensiona a su tamaño correcto al mostrarlo pero haras trabajar mas a la GPU y en ciertos casos CPU).
Todo lo que se ve en pantalla menos la tipografia son archivos de imagen en gormato .PNG y los wallpaper en formato .JPG. (barras, iconos de apps, separadores, botones... todo son imagenes)
Cada aplicacion tiene los suyos propios y aparte el sistema tiene los suyos en /system/framework. Por supuesto la capa tiene tambien su "mini-fremwork".
Son todo archivos .APK que se pueden asociar a winrar, winzip, 7zip... y podras comprimir y descomprimir sin problema para cambiar estos archivos (ojo con el resto como .XML y otros, para tocar estos si necesitarias descompilar la app, editarlo y volver a compilar).
IMPORTANTE: veras ciertos archivos .9.png esto mejor ni tocarlos sin saber lo que se hace. Tienen propiedades para estirar ciertas parte al mostrarse en pantalla (alguna barra, menus pop-ups, etc...). El simple echo de abrirlos con editor fotografico y guardar de nuevo sin tocar nada se perderan esas propiedades.
Lo minimo que puede pasar es que se muestren deformados, lo peor es que cualquier app que intente mostrarlo de FC. Si es por ejemplo la barra de notificaciones que se muestra continuamente no llegaria a arrancar ni el sistema, seria FCs continuos sin parar ni dejar hacer otra cosa (incluso puede llegar a ser un suplicio el lograr reiniciar el movil).
Para los .9.PNG tendrias que buscar tutoriales especificos, que existen muchos, o usar unos ya echos que sepas no den problemas (siempre que se mencione en los creditos cuando se publique el tema de donde salio y quien lo diseño).
EDITO: es posible que despues de hacer los cambios tengas que firmar el .APK. Para eso tendrias que buscar algun programa para windows o alguna kitchen para linux (algunas tienen tambien version de windows pero es mas dificil de encontrarlas).
Por otro lado existe otra opcion que simplifica mucho todo una plantilla creada por los grandes Jrsoft e Intronauta que inyecta directamente los PNGs desde recovery a cada .APK
http://www.htcmania.com/showthread.php?t=258333
O la replica en la que se basaron estos 2 maquinas de una plantilla muy similar en XDA en la que se basaron y mejoraron a su manera.
Aun existe otra opcion mas, siguiendo un sistema similar a esas 2 plantillas. Exites casi desde los inicios de Android una app llamada Metamorph que hace lo mismo con el SO arrancado, obviamente es mas agresivo el cambio que desde recovery pero no deja de ser una opcion mas. Al igual que la plantilla existe una replica Española con igual nombre creada por Tolemac y Super@tmel mucho menos agresiva (aunque no dejan de ser cambios demasiado importantes para estar con el SO arrancado, es mucho menos dañina), pioneros españoles en la cocina y desarrollo de android adelantandose en algun momento incluso a CM con ROMs funcionales cuando Cyano aun no queria ni tocar Eclair aun (lentas y con muchos FCs, Super@tmel logro una Eclair para HTC Magic funcional y casi tan rapida como Donut a falta de drivers de video para hacer videos, de eso ya se encargo Codeworkx para CM meses despues los los progresos del super)