A really good program you can use is Handbrake. It's a very popular program among so called "pirates" because it's really good at getting a high quality even at tiny file sizes. And this is with good reason, because the main purpose of Handbrake is, indeed, to make the movies small with high quality. Personally I use it when I distribute my short movies on the internet, and it works like a charm. But enough talking, let's get to the settings!
Let's start with the beginning and go through the important settings.
On the right you have a presets panel. Choose Regular -> Normal or Regular -> High Profile.
Now, we start with the Picture settings.
The anamorphic setting is about the aspect ratio. So you've probably heard about the fact that in video, pixels aren't always square. So if you have widescreen footage, if you compress that to be much thinner, like an OLD SD TV, you could tell the video player to make each pixel wider than it actually is. So, you started have a 500 wide picture, you compressed it to 300, then you tell the player to make those 300 as wide as 500 again.
This is just a basic idea about what it is. You can just leave it at Loose with Modulus at 16. But if you want to learn more and squeeze the absolute maximum out of the file, read about it here.
Leave the cropping at Automatic, unless you want to crop.
Then we go over to the Video Filters. You can turn all of these off. They are made to correct bad footage, which you've probably already done in your video composing software..
Now, Video. These are the crucial settings. Use H.264. This is the format that gives you the highest quality compared to file size today. Quality. This is THE setting if you only want to set ONE. Set it to Avg Bitrate. This is the best one because if you have a lot of blacks in the picture (at night), you can optimize for that and get even smaller file sizes, but at other points in the movie you'll need more space, and so average is the best here. Notice that the size is in kbps which means kilo-bits-per-second. One kilo is 1000 (not 1024, that's kibibit.). One bit is 1/8 of a byte. So if you want a 10 second movie that's 1 MB, you want to enter 1 MB = (1024 * 1kB * 8bits) / 10s = 820 kbps.
Remember that the audio will also add up in addition to this. You just have to test some values until you get an acceptable quality that's small enough for you. If you enable 2-pass encoding, it will evaluate the movie twice, which means smaller file sizes compared to the quality, but it also means that you need more CPU (computer power) to watch it. So turn it on if you want to watch it on computers, leave it off if you want to watch it on mobile phones/tablets.
As for the audio, you just set it to what the output of your original file is. The sample rate of most movies is 48 kHz, but if you recorded in 44.1 kHz, set it to 44.1 kHz... As for the bit rate, 160 is acceptable, but if you have high quality mics and music, set it to 192. You can go higher than this, but as you want small file sizes, there is no need. You could also go lower depending on what size you want to end up with. But do a Preview and listen to the result until you are happy with it.
Then, the last thing you need to do is to tick off "Large file size". You need to have this on if the file is going to be larger than 4GB, but it will break compability with a lot of devices if you leave it on. Then you turn on "Web Optimized". It will make your movie better suited for progressive download so you can shuffle in the movie without downloading it all. But if you are planning for your users to download the whole movie as .mp4 and watch it on the computer, leave it off.
Now, set a file name and click Start. You can also Preview a small clip when you're testing the bitrate setting. Make sure that the extension is .mp4 and not .m4v. This isn't important, but you asked for .mp4, not .m4v. It's just the extension that is the difference anyway..
Hope you get your video squeezed down in size and yet keep the quality as high as possible! Good luck :)