Twine 2 is the most recent release series of Twine. If you've never used Twine before, this version is recommended.
Twine 1 was the original version of Twine, and is still available to download for Windows and Mac.
Story formats are separate from the Twine editor, and determine the markup and code you use to write your stories. They allow you to add conditional logic, display effects, and other interactivity. (How do I decide which story format is right for me?)
Harlowe is the default story format for Twine 2. It isn't available in Twine 1, and features newer, different markup and macros from Twine 1's formats.
SugarCube is a popular format descended from Twine 1's default, Sugarcube. Twine 2 comes packaged with the latest in the SugarCube 1.x series, but there's also a 2.x series available that can be added manually.
Twine stories are published in HTML format, which means you can publish your files on any web server.