[apristel]

Basically if you want themes and stuff you want Deodexed.

from a post on XDA..

Deodexed ROMs have their .apk's (which are basically the application packages) repackaged in a certain way. An "odex" can be thought of as a collection of parts of applications that have been pulled out and optimized before booting. This speeds up the boot process - in a way, it preloads part of the applications - but it also makes hacking those apps difficult because part of the original code is already extracted somewhere else.

Deodexing is just a process of putting those pieces back into the original applications. It takes a while to extract those parts and build the .dex cache (aka Dalvik cache), but only because the relevant parts aren't in an easy-to-access place for the system. The advantage of this is that an app can be modified effectively and the developer doesn't have to worry about conflicts from the separate odex part of the code.

So, short version: "Deodexed" ROMs have all their apps put back together. If an app can be themed, for example, a deodexed version of that app will not get messed up when the modified .apk tries to mesh with the odex of the original un-modified .apk. Because it's not there.

If you want an aftermarket theme, you need a deodexed ROM. I'm not sure if deodexing can be done to individual apps within a non-deodexed ROM.