I need help getting my head around the difference between my current OOP notion of state, and the way it would be done in a functional language like Haskell or Clojure.
To use a hackneyed example, let's say we're dealing with simplified bank account objects/structs/whatever. In an OOP language, I'd have some class holding a reference to a BankAccount, which would have instance variables for things like interest rate, and methods like setInterestRate() which change the object's state and generally return nothing. In say Clojure, I'd have a bank-account struct (a glorified hashmap), and special functions that take a bank-account parameter and other info, and return a new struct. So instead of changing the state of the original object, I now have a new one being returned with the desired modifications.
So... what do I do with it? Overwrite whatever variable was referencing the old bank-account? If so, does that have advantages over the state-changing OOP approach? In the end, in both cases it seems one has a variable that references the object with the necessary changes. I have only a vague concept of what's going on.
In a pure functional style, you'll never overwrite any variable.
An analogy would be to spacetime in physics. If you consider the world as 3d, then objects don't have fixed positions - they move over time. To bring math to bear on the physical world, we therefore add a time dimension and consider the values of various properties at particular times. In doing so, we've made the objects of our study into constants. Similarly, in programming, there is a conceptual simplicity to be had by working with immutable values. Objects with an identity in the real world can be modeled as a sequence of immutable values (the states of the object at increasing times) rather than as a single value that changes.
Of course the details of how to associate the sequence of values to an "object identity" can be a little hairy. Haskell has Monads that let you model state. Functional Reactive Programming is a more literal attempt at modeling objects in the world with pure functional updates, that I think is a very promising direction for programming.
I will note that Clojure, unlike Haskell, isn't pure, and you can update variables as you suggested. If you're only updating a few variables at a high level, you'll still probably enjoy many of the conceptual simplicity benefits of functional programming.