A First Day Cover is an envelope or post card with an affixed postage stamp that has received a special first day of issue postmark. When a new stamp is ready to be released to the public, it typically debuts in a specific city or region - usually a city which has something in common with the theme of the stamp. For example, an Andy Warhol stamp would probably be released in Pittsburgh, Pennsylvania, while a Wright Brothers stamp might be issued first in Kill Devil Hills. On this first day, the post office will cancel mail sent with this stamp with a special post mark. The postmark usually says "First Day of Issue", and often has a special design. In addition, the Post Office will often make special envelopes or post cards available that have designs related to the stamp. These specially designed envelopes are called cacheted covers and can also be purchased from a wide variety of companies specializing in philately.
With the exception of individual stamps, First Day Covers are probably the most collected items by philatelists. While stamps with postmarks are usually worth much less than those in unmarked, mint condition; first day covers are the exception and can become quite valuable over time. In fact, most stamp price guides list First Day Covers in their own special category beside the usual OG (Original Gum), NH (Never Hinged), and Used (Circulated/Postmarked).
How to Obtain a First Day Cover1
Obviously you can buy or trade them like any other collectable, but you can also get them free (almost) from the post office2. Up to 30 days after the original issue of the stamp, any stamp collector can request to have their stamp marked with the first day of issue seal. Here's how:
Purchase the stamp
Place it on a self addressed envelope or post card. It is usually best to place your address on a removable label so that you can peel it off and have an "unaddressed" first day cover.
Place that envelope inside another envelope addressed to the post office in the original city of issue (you can find the original city of issue at your local post office, usps.gov, or numerous stamp collecting web sites). Address it with the following:
<City of first issue>, <State abbreviation> <5-digit zip code>-9991
NOTE: While it is probably best to find the street address of the post office as well, this is not required.
You then just place it in your mailbox and wait for it to go there and come back.
Because your first day cover is sent back to you through the regular mail, it is important to note that you must affix the proper first class postage amount to the envelope regardless of the denomination of the stamp. For example, if the current postage rate is 37 cents and the denomination of the stamp is only 10 cents, you must add an additional 27 cents to the envelope. Quite often, the post office will offer suggestions of additional stamps to bring you up to the required postage. These suggestions usually match the theme and/or colors of the stamp so that they don't look out of place.
1This writeup was aimed at United States First Day Covers. Other countries offer FDCs as well, but their rules may be slightly different.
2You can also order new first day of issues by phone or online, but that takes all the fun out of it.