A step file is a file containing instructions for a rhythm game simulator (such as Dance With Intensity or StepMania). The four most common formats for step files are MSD, DWI, SM, and BMS.
MSD files were the original format for Diet Diet Revolution, a Japanese-made simulator of Dance Dance Revolution. They are still supported by a few programs, including Dance With Intensity.
DWI files were derived from MSD files and first used in Dance With Intensity. SimWolf, one of the creators of the program, used this to quickly implement the concept of freeze arrows into his simulator as well as a few more neat features. MSD files may be played as DWI files by simply changing the file extension and altering the #GAP value (which measures the difference in the beginning of the song file to the beginning of the actual song). DWI is supported by most simulators today. They, too, emulate only Dance Dance Revolution.
SM files are StepMania's way of supporting just about every music-related arcade game out there in one format: Dance Dance Revolution, Pump It Up, EZ 2 Dancer, and ParaPara Paradise. It also has the beginnings of support for stuff like BeatMania, Guitar Freaks, and DrumMania, even though those require more varied hardware than the program itself wants to handle yet. The official specifications for the SM format are available in the StepMania readme, which may be found in the sources at the bottom of this writeup.
BMS files first showed up in the Japanese simulator Delight Delight Reduplication. I can't find out much, because all the documentation is in Japanese. The format's also supported by Dance With Intensity and StepMania.
Step files may also be called SimFiles, since they're used with simulators.
http://www.stepmania.com/stepmania/readme.php - StepMania readme, including SM file specifications.
http://www.geocities.com/moon_jihad/smtute.html - A nice tutorial on making an SM file.
http://www.ajworld.net/simfile_types.txt - The be all, end all of step file information. I found this during my research and lost my will to go all-out in this writeup, because someone already had and knew ten times as much as I. I'm so depressed.