Any object, concept, or piece of information used to solve a puzzle.
A piece can isolated, treated as a distinct entity, even if it physically attached to another game world object. Not all game world objects are puzzle pieces. Only things that can be associated with a puzzle are puzzle pieces. Everything else is thematic decor.
This definition of puzzle piece correlates well to what somebody means when they say, "ah, I've found another piece of the puzzle." You can freely say this if you've found an actual object, some scribbles on a wall, or while reading a character's diary. In all cases you've identified some isolated component of information that you know relates to a puzzle.
Even though we tend to think about mental puzzles, this definition applies to physical puzzles as well. If a player needs to find a ladder to get up a wall, both the wall and the ladder are puzzle pieces. They need to be associated together to solve an environmental puzzle.
Acknowledging the flexible nature of puzzle pieces allows a designer to mix-and-match a variety of qualities when creating pieces. Many of the concepts of puzzle design apply equally, or adaptably, to any kind of puzzle piece. Some concepts are limited to certain kinds of pieces. By recognizing which is which we can provide variety where possible.
Assume everything in this reference is a working draft, there's prone to be some mistakes and inconsistencies. I figure it's best to publish and get feedback rather than write for years in secret. The terms will change, the structure will shift, and the bugs will be chased out. It'll take a while.