The Minecraft community has created dozens of programs that can be used to enhance the game. Server software is so numerous that it has a page of its own. The most popular programs are Mappers that create an overhead view of a level. Map Editors let you directly alter a level outside of the game. Level Generators create new terrain types and block patterns that aren't available normally. Finally, there are Specialized Programs for editing your inventory, simulating Redstone circuits, and altering game files at a low level.
Mappers
Overhead mappers create a literal map of your level's terrain. Many mappers have options for different overhead and angled modes, and some will limit the map to selected block types or slice the map into smaller pieces.
Infdev Map Visualizer
Created by Notch for Infdev levels before he renamed the game to Alpha. Official site. Alpha only.
Isocraft
The first of its kind. Creates a top-down image of a Classic level. Isocraft is the only overhead mapper to use a 30 degree angle. Forum thread. Classic only.
Cartograph
The first mapper for infinite levels. Created for Infdev levels before Infdev became Alpha. Java and Windows binaries and source code are available. Forum thread. Alpha only.
pynemap
A cross-platform mapper written in Python, found to work on Windows, Linux and OS X. Source code is available. Forum thread. Alpha only.
Minecraft Topological Survey
A cross-platform mapper written in C# .NET, found to work on Windows, Linux and OS X. Source code is available. Forum thread. Alpha only.
c10t - map to image generator
A rewrite of Cartographer. Potentially cross-platform. Linux binaries and source code are available. Forum thread.
Map Editors
Map editors alter a level's terrain or other properties, such as player position and time of day. Some of them also let you edit your inventory and generate terrain.
Omen
The first map editor, created to edit Classic levels. With it, you can view the level's blocks in 2d slices, and alter them by "painting" blocks using brushes of different shapes and sizes. Also includes some terrain generators and supports the deprecated Indev levels. Forum thread. Classic only.
NBT Forge
A successor to Omen that supports the newer Alpha levels. Like Omen, you can view 2d slices and paint blocks using a different set of brushes. Forum thread. Alpha only.
MCEdit
The first 3D editor. Created to import older levels into the new Alpha levels. Fly around in 3D and select blocks, then copy or export them. Import blocks from schematics or from entire Classic levels. Forum thread.
MineEdit
All-in-one Editor. Includes a terrain editor similar to Omen and NBT Forge. Replaces blocks of one type with another. Also lets you edit your player's inventory and the world's entities. Forum thread. Alpha only.
LolEditor
View the terrain with different viewing modes and show block statistics. Edit entities and inventory, and create randomized items. Forum thread. Alpha only.
Level Generators
These programs will either create a new level with custom terrain, or "implant" new blocks into an existing level.
ZOMG
Creates wild, surreal landscapes of several varieties. Forum thread. Classic only.
MCMapper
A dungeon generator seemingly inspired by old Roguelike games. Creates rooms and levels out of different materials, in different styles. Rooms may hold traps, statues, enemy spawns, and/or treasure. Forum thread. Alpha only.
Specialized Programs
INVEdit
An inventory editor that lets you add and remove items. Also exports your entire inventory, to copy between levels or use as a preset. Forum thread. Alpha only.
Redstone Simulator
A simulator for Redstone circuits. Place circuit elements in a grid and use Play/Pause to control the simulation. Forum thread. Alpha only.
NBTEdit
Development tool for working with the NBT format used by different level files. Can be used to edit inventory, entities, and world attributes. Forum thread. Alpha only.