Longtime Amazon employee here: I don't recall when Amazon started awarding puzzle pieces, but it was sometime before 2008. Audible (an Amazon company) has a writeup of the practice: http://stn.audible.com/patents/
In short, the pieces are transparent Lucite, about 4" square and 1" thick, with tabs & slots that fit with other identical pieces. A Google image search for "amazon patent puzzle pieces" will give you a good idea. They award colorless pieces for submitting a patent, with generic "Congratulations on inventing something" wording. You get a blue piece with your name & patent number when the USPTO awards the patent, many years later.
That's it, no direct monetary award. So why do Amazon employees even bother? Two main reasons: 1) The process makes it extremely effortless for people to file for a patent: First, the inventors submit their idea in a very short description. Someone in the IP department reviews it for alignment with the business goals of Amazon, prior art & related work, etc. If they decide to move forward, the inventors will send the patent lawyers whatever documentation they have on the idea, and then have a meeting to talk it through. Maybe two, depending on the complexity. The lawyers will then draft the patent application, and send it out for review & feedback. Another meeting to go through any feedback, and once the application is final, they'll submit it. In the end, for the employee it's a tiny incremental amount of effort on top of the work they've already put into developing & building the idea in the first place.
The 2nd reason people do it is that it is a natural side-effect of the "invent & simplify" culture. There is a large breadth of teams at Amazon, each trying to solve deep problems within their domain. This creates no end to the number of interesting problems requiring workable, but creative solutions. The kind of people who enjoy doing this kind of work find it naturally rewarding, and they're also recognized for it in performance reviews & promotions, which then leads to higher compensation.