Records are very rare, and 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, and can also be found from chests in dungeons.
These records play music made by C418 as he is the official Minecraft music composer.
The Gold record's DEC code is 2256. The Green Record's DEC code is 2257.