state means that something is being stored somewhere so you can refer to it later.
Creating a variable, creates some space for you to store some data. This data is the state of your program.
You use it to do things with, alter it, compute with it, etc.
This is state, whereas the things you do aren't state.
In a functional language, you mostly deal only with functions and passing functions around like they were objects. Though these functions don't have state, and passing the function around, introduces no state (besides maybe inside the function itself).
In C++ you can create function objects, which are struct or class types which have operator()() overloaded. These function objects can have local state, though this is not necessarily shared among other code in your program. Functors (ie function objects) are very easy to pass around. This is about as close as you can imitate a functional paradigm in C++. (AFAIK)
Having little or no state means you can easily optimize your program for parallel execution, because there's nothing that can be shared among threads or CPU's, so nothing that contention can be created about, and nothing you have to protect against data races, etc.