1. Download MCEdit

Start by downloading MCEdit from the MCEdit website.
MCEdit is available for Windows, Mac, and Linux.
If you're having trouble running MCEdit you can report an issue.

Note: MCEdit is no longer being updated by codewarrior0 and is being continued by a small group over on Khroki's Fork. There you can find updates for 1.8 and up.

2. Select the region around your map

Select a region that is just large enough to contain your entire map. Include at least a few blocks of empty space around the map. You can click "Select Chunks" to see exactly what will be included in the pruned map.

Note: Do not prune chunks inside the rectangle, as this will make the map difficult to work with. A few empty chunks will make no significant difference in map size.

3. Click "Chunk Control"

Click the Chunk Control button on the bottom right.

Note: You must be in "Chunk View" in order for this to work.

4. Prune and save

Now you can prune the map by clicking the Prune button in the sidebar on the left. That’s it! Your map is now pruned. Save with CTRL+S, then you can close MCEdit. Be sure to remove any folders or files generated by MCEdit.