Mission editor for general work.
Notepad to make specific changes to a map.
Torque Constructor, Quark, WorldCraft/Hammer, or GTK Radiant for interiors.
You can use almost any program to make an interior if you know how. No one will teach you how to do it though and unlike the 4 programs mentioned before which basically force you to make an interior correctly, the other programs don't have these sorts of features and constraints. So if you don't know what you are doing and don't do things right your map just won't work and you won't know how to fix it. Believe it or not, you can actually make an interior in notepad, .map files are pretty much just lists of shapes and textures in plain text.
If you need to make interior based terrain use Nem's Mega 3D Terrain Generator (check google).
Make skies in terragen using the terragen skybox script on the valve developers wiki (google again).
You can do hieghtmaps in terragen too.
Texture work can be done in any photo editing program. I use the GIMP (
http://www.gimp.org/). You can find textures online, there's a thread in this forum that has a list of lots of sites. You can also just go out and photograph them. Personally I bring in small samples and scan them on a scanner. The textures in my map "Under Construction" were made by scanning small pieces of 2x4s and drywall I had lying around in my garage.
That's pretty much all the tools you can use for making maps worth mentioning. If you need any other programs for a specific task, check
this forum thread first.