A state machine (sometimes more precisely referred to as a finite-state machine) is a way of representing the operation of a block of logic which includes state, i.e. retained information.
Formally, a state machine consists of a list of states, together with a list, for each state, of what inputs can cause it to transition to another state, and what state it transitions to.
Many processes in a computer (e.g. handling an interrupt) can be modeled as state machines; given a state machine, it is relatively straight-forward to produce hardware which implements that state machine.