I have created a 4 minute screencast showing how to convert videos and movies so they will play on the Blackberry Bold, Curve 8900 and the Storm.
I reference Lifehacker and the post Top 10 Free Video Converters. You can find a list of software there. I myself prefer Clone2Go Free version which is demonstrated in the screencast. Hope this helps!