What is a good way to define "state", as in state variable or state machine, to a new (previously non) programmer? What are some good ways to explain why this concept is useful for writing software? Is the concept of state explicitly taught in beginning programming courses or books commonly?
"state" is needed, when you need to remember something. Functions (not "methods" or whatever) ideally only depend on their inputs. If you ask a question where the answer can change over time, even if the inputs are the same, you need something to remember that difference in the answer, correct? Otherwise, you are unable to give a different answer because no other factors have changed (let's assume the answer does not depend on time directly).
That "thing/information" that you need to remember is called "state".
(it is not requiered that this "state" changes over time, it's basically just a way to say "remembering/knowing something")
State commonly refers to either the present condition of a system or entity...
That's pretty much what it means in a computing context: the data that defines the condition of some object or system.
The meaning of 'state' isn't specific to programming. There are examples of 'state' literally everywhere you look. The television is off. The coffee is hot. The sneakers are a) blue; b) smelly; c) not put away; d) quite worn out. 'state' in a programming sense is just the same as 'state' in a non-programming sense, except we apply it to the objects that we deal with: variables, objects, threads, databases, file systems, etc. If you have to explain it, explain it in terms that are familiar -- there's no need to make it into a foreign, technical concept.
A clock is a good example of a simple system that has some state: a clock can be running or not running, and it indicates a time which may or may not correspond to the actual time of day. It's pretty easy to see how those things are like variables and how changing the state of the clock might impact other things.
Compare that to something stateless, like a statement: "The door is red." The statement itself doesn't have state. It may or may not be true that the door is red, but the statement itself doesn't contain any state. Painting the door can change the truth of the statement, but the statement itself never changes. Similarly, a number like 42 doesn't have any state: 42 is 42 and there's nothing you can change about it.
Variables have state, values don't.
You can use the analogy of a traffic light which can be in one of three states: [GREEN], [YELLOW] or [RED]. It must only be in one state at a time. The traffic light is the actual state machine being modelled. It will normally transition its state from [GREEN to YELLOW], then [YELLOW to RED], then [RED to GREEN].
An alternative state transition (which is in effect in some countries like UK, has two transitions of [RED to YELLOW, then YELLOW to GREEN] in place of the [RED to GREEN] transition.
State is information your program manipulates to accomplish some task. It is data or information that gets changed or manipulated throughout the runtime of a program. The "state" of a program at a given time refers to a snapshot of all the data the program is currently looking at or analyzing to get to the next step in it's execution.
My university started with Scheme, so we started programming with a state-less model. We then switched to C and were very explicit about what state is, why it's useful, and why it makes things potentially very complicated. So some universities certainly talk about state, but not necessarily all of them