Records play in Jukeboxes and are very rare not very rare due to the method described below.
Not much is known about them yet, comments on Notch's blog post seem to indicate that they can be found as loot from killing creepers. If a creeper is killed by a skeleton it will drop a record of either color. Whether this is a bug or intentional is unknown. Records can also be found from chests in dungeons.
These records play music made by C418.
The Gold record plays the track "13". Its DEC code is 2256.
The Green Record plays the track "Cat". Its DEC code is 2257.