The terminology isn't absolute when applied to actual languages. Usually "stateful" refers to holding the "state of the computation" largely in variables of some sort (variables = changeable references to values). These can be ordinary variables (C) or fields of objects (C++, Java). It is possible in many such languages, however, to minimize such state and to program largely with constants only and with parameters of functions and methods. The latter can be variables or constants, depending on the language.
The reason that stateful languages can be programmed this way is that they also employ a run time stack in which values can be maintained.
Stateless programming in most commonly done in functional languages that minimize the use of variables, depending on constants and constant function arguments. The computation "state" is the stack itself. However, most functional languages do have some mechanism for declaring variables (things which vary), though they also tend to call names that refer to constants as "variables" confusing the issue somewhat.
In "pure functional programming" you utilize only constants and immutable function arguments to move values around the computation. The "State of the Computation" is the state of the run time stack. This is true Stateless programming.
Most imperative and OO programming, on the other hand is stateful. The "State of the Computation" is comprised of both the state of the run time stack and the currently referenced values of the variables.
Another way to think of it is that in stateless programming, the state is "implicit" in the stack and the current program pointer. In stateful programming, the state is explicit in the variables and fields (to a large part - there is also the stack).
