How to deodex an odex file

In the latest version (v1.4.0) of baksmali the process has been greatly simplified:
baksmali -a <api_level> -x <odex_file> -d <framework_dir> -o <output_dir>

Eg. to deodex the Google Services Framework system app (from Jelly Bean), you can do the following:
  1. First of all, fetch the dependencies: apktool and baksmali
  2. Copy the /system/app/GoogleServicesFramework.apk and /system/app/GoogleServicesFramework.odex files (and the /system/framework folder) to your computer.
  3. Initialize apktool using the downloaded framework folder:
    apktool if framework/framework-res.apk
  4. Unpack the contents of the target app's APK using apktool:
    apktool d GoogleServicesFramework.apk GoogleServicesFramework
  5. Read the API level of the APK using aapt (which is a helper app for apktool):
    aapt d badging GoogleServicesFramework.apk | grep targetSdkVersion
  6. Disassemble the contents of the ODEX using baksmali (specify the correct API level with -a):
    baksmali -a 16 -x GoogleServicesFramework.odex -d framework -o GoogleServicesFramework/smali
  7. Repackage into an APK:
    apktool b GoogleServicesFramework GoogleServicesFramework-deodexed.apk
  8. Optionally sign the package (with a key named "my_key" using the my-release-key.keystore file for keystore):
    jarsigner -sigalg MD5withRSA -digestalg SHA1 -keystore my-release-key.keystore GoogleServicesFramework-deodexed.apk my_key
    (jarsigner is part of the Oracle JDK)
  9. Optionally run zipalign to give the APK the finishing touches:
    zipalign 4 GoogleServicesFramework-deodexed.apk GoogleServicesFramework-deodexed-aligned.apk
    (zipalign is part of the Android SDK)
P.S.: if you want to know what an odex file is and what deodexing means, read this short guide