An "odexed" app is an Android application that has the compiled byte-code (dex) for the classes bundled with it.

What does odex/deodex mean?

An "odexed" app is an Android application that has the compiled byte-code (dex) for the classes bundled with it. So "odexing" means bundling the byte-code with the apps, while "de-odexing" describes the reverse process.

Some Background, please!

"DEX" is an abbreviation for "Dalvik EXecutable". So that's what usually gets executed when you start an app. Those .dex files are located in the Dalvik cache (usually /data/dalvik-cache, but locations might differ). On installation of an app, its DEX code needs to be placed in the Dalvik cache -- or the Dalvik VM could not execute it.

Odexed apps

When Android runs the application for the first time, the VM has to extract the dex bytecode from it and place it in the cache belonging to the virtual machine. This results in faster start up time initially but, it's harder to modify, for example, theming and repackage it again.

De-Odexed apps

When Android runs the application for the first time, the VM has to build the dex bytecode from it and place it in the cache belonging to the virtual machine. This of course takes a little longer than just copying it, but its not only easier to modify (theming etc. again), but also easier portable for different target architectures, as the DEX is specifically designed for it.

Further readings on this site