The main difference between a FSM and a statechart is the compositionality aspect of the two formalisms. The FSM can be combined using the OR and the AND operators: the AND operator produces a number of states that is equal to the cartesian product of the original states of the two FSMs that are conjuncted. This means that you are limited in the usefulness of the FSM by the number of interactions between systems, because the number of states increases exponentially.

The statechart solves this problem by using a representation that allows both OR and AND avoiding the state explosion. Multiple states can be combined in a super-state, which allows to model common properties of the enclosed states, provided that the internal substates are XOR-ed, i.e. only one of them can be active in a given time. The advantage of the super-states is that they allow the specifier of the system to proceed in a top-down manner by specifying iteratevily the complete behaviour of the system. These super-states can also conjuncted, to model the interactions between the systems and to represent their parallelism. This conjunction creates implicit interactions between the two subsystems, which substitute the need to create the product FSM.

Both FSM and statecharts can represent the same behaviour of a system, but they differ in how easily understandable their representation can be for complex systems.

>I read the article, and then beyond, and I still don't know what in tarnation distinguishes an FSM from a simple state.

Well, FSM is a basic CS concept.

>Every program has a set of states and transitions. Is the difference simply that in an FSM the programmer has modeled both sets explicitly? And if so, what is the model -- a map from states to available transitions?

Yes, and actions on each transition.