A more paradigm-neutral notion of declarativity is that you separate intent (the function or relation that your program is to compute) from execution (the shoveling of bits that goes on in the actual execution of the program).
For example, SQL or LinQ are declarative fragments embedded in an otherwise imperative/OO language, since you specify the intent, and behind the scenes, the database's query optimizer or the LinQ API can do all the optimizations they like because you've specified your intent and not a concrete plan for execution.
In Haskell, treating state as data to be passed around has the advantage that you can also fork the state if you want to try out alternatives (i.e., search).
Which means, you don't remove side-effects from OO code. You institute a contract between some provider of a declarative framework (that allows you to specify intents) and the consumer of said framework (who is supposed not to poke around in any state that the framework works on).
I.e. state is seen in functional programming as undocumented API calls in imperative programming. In rare cases you need them, but you want to only use them where you actually get an advantage out of it, because it's bound to get in your way at some point if you're not careful.