Most Nokia handsets feature symbian s60 platform v9.0 and upwards. Natively they have option to record and play MP4 files with MPEG-4 part 2, which is h.263. Higher end Nokia mobiles like N8 will support mp4 files with MPEG-4 part 10 H264 codec. This means that most videos you find on the internet viz. youtube will play on these devices.

However for little older models like Nokia e63 ,71,e72,5800 mp4 files with MPEG-4 part 2 (h.263) codec are only supported.

To convert media files to be played nokia mobile phones Use Handbrake, a GUI tool to convert media files to be used for Apple products like iPod, iPhone and the iPad.This is an cross platform tool that works on Mac, Linux and Windows.

Launch handbrake, and choose Normal preset shown on the right of the screen.

Container: MP4

Video Tab:
Video Codec: MPEG-4 (FFmpeg)
FrameRate: Same as Source
Avg Bitrate: 240 or 320 (Depending on the quality you want, for small screens such as e63,
a 240 kbps bitrate looked fine.
Audio Tab:
Audio Codec: AAC
Mixdown: Stereo
Bitrate: 96
Subtitles: Add subtitles if any.

Picture Settings:
Anamorphic: Off
Size: Choose 320 as the width , select keep aspect ratio so the correct height is selected.
Generally its 320×240 or 320×176

Save the preset and give it a name like ‘nokia mp4’.

To encode video files for Nokia mobile phones the best option in Ubuntu is by Far Handbrake. Although you can compose few scripts using mencoder to encode video files, but still the best transcoder for movie files is still Handbrake.

For more info on MPEG-4 codecs check this post here.