Nokia and other current smartphones use a video format called 3GP. 3GPP, 3GPP2 are the new worldwide standard for the creation, delivery and playback of multimedia over 3rd generation, high-speed wireless networks. Defined by the 3rd Generation Partnership Project and 3rd Generation Partnership Project 2 respectively, these standards seek to provide uniform delivery of rich multimedia over newly evolved, broadband mobile networks (3rd generation networks) to the latest multimedia-enabled wireless devices. Tailored to the unique requirements of mobile devices, 3GPP and 3GPP2 take advantage of MPEG-4, the standard for delivery of video and audio over the Internet.

Nokia provides a video converter software.  Its slow and works only on Windows.  Since I can mount Nokia mass-storage directly on my openSUSE11.1 laptop, I decided to use ffmpeg to convert videos.  You can copy the converted files to your Nokia device over cable or bluetooth.  Video Center recognizes the new video file and list them in the list of available videos.  I use h264 + AAC codecs which provides the best quality/compression rate for Nokia phones currently.  Surprisingly, I found this works better compared to Nokia’s software on my phone

Here is the script. Usage is very simple.
videoencode.sh source_file dest.mp4

#!/bin/bash

ffmpeg -y -i "$1" -acodec libfaac -ab 72k -s 320x240 -aspect 16:9 -vcodec libx264 -b 300k -qcomp 0.6 -qmin 16 -qmax 51 -qdiff 4 -flags +loop -cmp +chroma -subq 7 -refs 6 -g 250 -keyint_min 25 -rc_eq 'blurCplx^(1-qComp)' -sc_threshold 40 -me_range 12 -i_qfactor 0.71 -directpred 3 "$2" > /dev/null