The first issue is card type. Compact Flash seems like a good choice overall, but there are also Smart Media, SD/MMC, xD, and Sony's Memory Stick, and newer, physically-smaller formats arriving every year. If you have other digital-storage devices, it may be convenient to have a common format.
I first chose to standardize on Compact Flash ("CF"). In general, it seems that the higher-end and professional cameras use CF, so there's an upgrade path. This may be because CF is a physically larger format than many of the others, so it tends to be available in higher capacities, or at lower prices for the same high capacity. But for most people these may not be compelling considerations.
Indeed more recently I've also taken on Secure Disk ("SD"). This seems to be a common format among smaller devices, not just cameras, but also GPS devices, etc.
Capacity is a very important topic. You will want to buy a bigger card. Cameras tend to come with unrealistically-small memory (a.k.a. "flash") cards. Many come with an 8 MB card, which will fit only 4-5 full-resolution, low-compression pictures! If I'm somewhere special, like a family wedding, or an exotic location, then I can easily take a hundred pictures a day. Highest-quality pictures (high resolution, low compression) can consume about 1-3 MB each, or more for RAW images.
If you're on a long trip, and use up the card, you don't just run out and buy another one, since they may be hard to find, so you need a large card, or be diligent about erasing the less-good images, or ideally be able to download them to another device, like a laptop. Luckily, multi-gigabyte cards have become quite affordable. But as camera sensors get bigger, image files get bigger. For instance, full-frame RAW files can be 12+ MB in size, so on a longer trip taking hundreds of pictures, one still has to deal with exceeding memory card capacity. (I typically carry a laptop, in part for that reason.)
Back in the day, it was common to spend $100 or more on a large-capacity memory card, which may have been a mere 128 MB. As I write in 2008, one can get 4 GB cards for $50 or less. There used to be "digital album/wallet" devices, which combined a card reader with a small hard drive. In practice they were expensive for what they were.
Really small cameras may use expensive, custom re-chargeable batteries, and they still don't last that long. It may be necessary to buy an extra one, and make sure both are fully charged every day if you're on a trip. Larger cameras will take higher-capacity batteries, or even take standard AAs, which is definitely a convenience (and a very valuable backup "in the field"). To save money (and the environment), get high-capacity re-chargeable AAs, like NiMH (Nickel Metal-Hydride). These are expensive up-front, but a good deal in the long run.
Battery life is an issue, though getting less so. Especially expensive are using the LCD screen, built-in flash, downloading via USB, and simply writing large images. A small camera with a tiny battery may only get 40-50 high-resolution, low-compression shots. Or one might get hundreds of shots using AAs, selecting higher compression to write smaller files, or avoiding the LCD screen. In general, camera electronics and batteries are getting much more efficient: with new cameras, I routinely get many hundreds of pictures from a single battery charge.
It is annoying that batteries tend to be specific to manufacturers and even specific camera models. I got lucky with a range of Canon models over a number of years using compatible batteries and chargers, but I fear the next generation of cameras will force me to re-invest.
Copyright Richard Schooler, 2001-2008 firstname.lastname@example.org