Apps are spilt in 2 files apk and odex. The odex file is used for quick reference for the device and helps load your application quickly.
Deodex is when those two files are combine.
Odex is faster but deodexed allows for customizations. Most mods that people make will be for a deodexed system so if you plan on flashing modifications to your device via a custom recovery you want a deodexed system.
If you plan on flashing a rom that is odexed and not changing Anything than odexed makes your device run faster.
No, I'm not saying you should have read that first. I'm posting that link because there is an explanation there, and a link to an even more detailed one.