<p>When are objects or something else said to be &quot;first-class&quot; in a given programming language, and why? In what way do they differ from languages where they are not?</p>
<p>When one says &quot;everything is an object&quot; (like in Python), do they indeed mean that &quot;everything is first-class&quot;?</p>

In short, it means there are no restrictions on the object's use. It's the same as
any other object.
A first class object is an entity that can be dynamically created, destroyed, passed to a function, returned as a value, and have all the rights as other variables in the programming language have.
Depending on the language, this can
  imply:
being expressible as an anonymous literal value
being storable in variables
being storable in data structures
having an intrinsic identity (independent of any given name)
being comparable for equality with other entities
being passable as a parameter to a procedure/function
being returnable as the result of a procedure/function
being constructible at runtime
being printable
being readable
being transmissible among distributed processes
being storable outside running processes
Source
.
In C++ functions themselves are not first class objects, however:
You can override the '()' operator making it possible to have an object function, which is first class.
Function pointers are first class.
boost bind, lambda and function do offer first class functions
In C++, classes are not first class objects but instances of those classes are.  In Python both the classes
and
the objects are first class objects.  (See
this answer
for more details about classes as objects).
Here is an example of Javascript first class functions:
```
```
// f: function that takes a number and returns a number
// deltaX: small positive number
// returns a function that is an approximate derivative of f
function makeDerivative( f, deltaX )
{
    var deriv = function(x)
    { 
       return ( f(x + deltaX) - f(x) )/ deltaX;
    }
    return deriv;
}
var cos = makeDerivative( Math.sin, 0.000001);
// cos(0)     ~> 1
// cos(pi/2)  ~> 0
```
```
Source
.
Entities that are not first class objects are referred to as second-class objects.  Functions in C++ are second class because they can't be dynamically created.
Regarding the edit:
EDIT. When one says "everything is
  an object" (like in Python), does he
  indeed mean that "everything is
  first-class"?
The term object can be used loosely and doesn't imply being first class.  And it would probably make more sense to call the whole concept 'first class entities'.  But in Python they do aim to make everything first class.  I believe the intent of the person who made your statement meant first class.