How can I train voice recognition on ICS?
The setting should still exist, it's just a little bit more awkward to get to. The easiest way is to hit the microphone icon on the search widget (though I think anywhere it appears will work) to bring up the voice action dialog. There's a wrench in the top right of that dialog that opens the settings:



Tap that to open the settings page, which should have the checkbox titled "Personalized recognition" as in previous versions (tested on a Galaxy Nexus running CyanogenMod 9, Android 4.0.4).