Deodex basically takes the odex file and stuffs it into the apk as a classes.dex. First boot it dissembles the file into /dalvik-cache (i believe). Now there is basically 2 copies of the odex, one in the apk one in cache. This makes it "portable". This allows modders to work on the apks & easily change stuff. If you want themes or stuff like lockscreen fixes you MUST use Deodex.
Odex is how things come stock. It takes up less room but making modifications or taking apks from other roms is hard. You cannot use themes with this version!!