It seems to me the use of state machines is just in logic circuits, is that correct? If not do they have other uses, such as say in microcontroller programming? I'm quite new to the subject and wonder if there are programs to create state machines or is it just a matter of understanding how they work and taking things from there?
"State machine" is a very generic term for any process (electronic or otherwise) whose output is not simply a function of its current inputs, but also depends on its past history. In other words, it has "memory", or internal state information.
Electronic state machines started out as analogs of the mechanical state machines (including such examples as adding machines) that preceded them.
Your list of questions is far to broad to address here in EE.SE. You really need to do some Internet research on your own and then come back with more specific, focused questions.