My first year working in Japan, I decided that to improve my Japanese and blend in better (both at work and into the culture), I would send out cards to some of my coworkers. It was kind of hard work, but worth it I think. Got a lot of practice writing kanji, anyway!
One thing I really like about 年賀状 is their variety. I'm not really a big collector, but I enjoyed receiving and keeping all the different cards every year. The general theme of each year's cards depends upon the animal of that year, derived from the Chinese zodiac (十二支). The years I was in Japan were those of the cow, tiger, and rabbit, so most of the cards I've collected show those animals. Some cards are custom-made and sport family pictures, much like a lot of Christmas cards in the U.S.
In my experience, many foreigners in Japan don't bother with them and aren't really expected to. So if you do send some out, you may surprise your friends and coworkers. Doing so is a good way to get some back, too. Generally people start sending them a week or two before New Year's (the post office will hold them and wait until New Year's to deliver them), and then during the first week or two of the new year they will often send cards to people from whom they received but didn't originally send one. They often write "年賀状ありがとうございました！" (Thanks for the card) on the front as an acknowledgement.
If you're interested in trying to send some yourself or you've received a card and want to know the deal, here's an explanation for you.
The boxes at the top of the blank side are for the recipient's postal code and the space below that is for their name and address. The person should be addressed as 様 (さま). For example 田中様, 安田様, John Smith様, etc. さま is an honorific, much like さん, but is used to indicate even more respect and formality. Whether you write vertically or horizontally is a stylistic choice.
At the bottom, generally you write your name and address, though some people leave it blank or just write their name.
The *'s at the bottom represent two numbers that can be found on every New Year's card. Every year the post office holds a lottery. There are big prizes like computers, vacations, and TV's, and smaller ones like free stamps. The larger prizes generally don't have many winners, but the cheaper ones do. The winning numbers (or digits) can be checked online or at your local post office after New Year's. Generally the number on the right is the one you need to look at, but apparently some prizes are restricted by the letter of the digits on the left (A, B, or C). I have won a few stamps in the past, but never bothered to claim them.
Here's an example of a filled-out card:
On the front of the card you don't need to write anything, but you can scribble some personalized message, write some English just for the novelty of it, or use a set phrase (決まり文句).
For New Year's, you'll generally see/hear:
Both basically mean "Happy New Year!"
Anyway, the New Year's cards are one thing I kind of miss about living in Japan. If you're over there but haven't bothered with them, it's your call...but I recommend giving it a shot.
Update (12/19/11): One thing several people have pointed out in the comments that's worth mentioning is that writing something by hand on the card is considered the "right" way to make up a 年賀状 for someone. I guess having everything printed on doesn't show the right level of effort.
Jen of Perogies and Gyoza dropped a link for a New Year's card commercial featured right now on the JP Post website. I had never seen any of these before, but apparently there are a number of these commercials from years past. Here's a previous one (maybe from 2008, which I think was the year of the rat):