Weightlessness is the experience of apparently having no weight. This condition is also known as microgravity. The microgravity symbol, µg, was used on the insignia of the Space Shuttle flight STS-107, because this flight was devoted to weightlessless research (see picture in that article).
Weightlessness means a zero g-force: acceleration is equal to gravity.
What we humans experience as weight is not actually the force due to gravity (even though that is the technical definition of weight). What we feel as weight is actually the force of the ground (or whatever surface we are in contact with) pushing upwards against us to counteract the force due to gravity. A wood block in a container in free-fall experiences weightlessness. This is because there is no reaction to the wood block's weight from the container, as it is being pulled down with the same acceleration. The acceleration of the container equals the acceleration of the block, which equals the acceleration caused by gravity. When the container is at rest on the ground, however, the force on each piece of the block is not uniform. Because the block isn't accelerating, there is also a force upward that arises because the block is a solid. Each horizontal cross section of the block experiences not only the force due to gravity on it, but also the weight of whatever portion of the block is above it. Part of feeling weight, then, is actually experiencing a pressure gradient within one's own body. There is another aspect of the feeling of weight that a pressure gradient does not account for, an example of which is the way that our arms are pulled downward with respect to our body. This effect comes from the fact that something hanging is not supported directly via a pressure from the ground. In fact the effect is almost the exact opposite of a pressure gradient, it is a tension gradient. It occurs because each cross section of a hanging object, a rope for instance, must support the weight of every piece below it. So the short answer is that what we call weightlessness has nothing to do with whether or not we are under the influence of a gravitational force, but has to do with whether there are force gradients across our body. In free fall, every part of everything accelerates uniformly (assuming that there are no tidal forces), and thus a human would experience no weight.
An rocket ship that is accelerating by firing its rockets is a very different matter, though. Even though the rocket is accelerating uniformly, the force is applied to the back end of the rocket by the gas escaping out the back. This force must be transferred to each part of the ship through either pressure or tension, and thus weightlessness is not experienced.
So any time something is in free fall (under the influence of no forces but gravity) it experiences weightlessness. NASA uses this to great advantage on an airplane affectionately called the "vomit comet": this is an airplane that NASA flies in 6 mile long parabolic arcs, first climbing in altitude, then falling, in such a way that the flight path and speed correspond to that of an object without propulsion and not experiencing air friction. This is realised by propulsion and steering such that air friction is compensated and nothing else. The result is that people inside are not pushed towards the bottom or any other side of the plane, i.e. they are temporarily weightless.
Weightlessness for a more extended period of time is achieved in a spaceship outside the earth's atmosphere, as long no propulsion is applied; orbiting the earth this is the case except at moments that rockets are on for flight path corrections, and until reentry in the atmosphere.