More capacity is always better - and usually cheaper per gigabyte of capacity. Don't skimp: content always expands to fill capacity.
USB 3.0 is so much faster so you should always choose it, even if your recipient doesn't have a USB 3.0 computer port today. They will.
Look online. Brick and mortar stores are almost always more costly.
The cheapest add-on capacity is an external desktop USB 3.0 hard drive.
The smallest cheap add-on capacity is an external portable hard drive.
The fastest drive is a Solid State Drive or SSD.
Now for some products.
Stocking stuffers With sale prices down to as low as 40¢/GB from almost twice that last Christmas, thumb drives are thoughtful and thrifty. 64GB USB 3.0 thumb drives are recommended because they can hold dozens of videos and thousands of photos and they load much faster than USB 2.0 - great for travel.
Any photographer and most videographers would welcome another high-capacity - at least 16GB - SDXC card. Currently 32GB and 64GB seems to be the market sweet spot, available online for less than 50¢/GB.
Make sure you get Class 10, which should guarantee plenty of bandwidth even for AVCHD 2.0 video. Some high-end - $1,000+ - DSLRs benefit from even higher performance cards but those are the exception and not the rule.
Good brands include Ritek, Patriot, PNY, Lexar, Kingston, Verbatim, Corsair and SanDisk.
Upgrading a tired computer Nothing perks up an old computer like a new SSD. But SSD quality and performance vary, so stick to name brands - Intel, Samsung, Micron, SanDisk, Crucial, Seagate, Corsair, - with good warranties. Expect to pay about 75¢-$1.25 per GB, and more for the largest capacities. Other than capacity and warranty, don't worry about performance. They are all fast.
For those on a budget, the Seagate Momentus hybrid drives - that combine fast flash with large disk capacity - will give any notebook computer a nice performance boost for under $150.
The thousand year DVD A perennial complaint about digital data storage is that you may not be able to read it in a few years, whether it is optical or magnetic. But as I found torture testing the Millenniata DVD, that is no longer true.
You can buy an LG Blu-ray burner - the only brand currently certified by Millenniata, with more coming next year - for less than $100. And the media is available online for about $2.25 per DVD in bulk.
Great for sending out family albums of photos, videos and scanned documents. And don't worry, DVDs will still be readable in 30 years, just like LPs are playable today because there is so much content on them and the players are cheap.
Photographer For most home photographers an external 2 to 4TB USB 3.0 drive is dandy, even if they don't currently have the fast USB 3.0 port. Their next computer will. Portable drives are handy for travelers and the space-constrained and cost around $100.
Movie buff Home media servers hook up to your home network and can stream music, movies and video to your TV or home theater with the right connections. Synology seems to have cornered the market on home media servers and I've heard good things about them from friends. But getting the entire set-up from storage to TV to work is not a job for the technology-challenged, so be prepared to get help if you can't figure it out.
Wi-Fi storage Tablets are generally light on internal storage - vendors charge ridiculous prices for added storage, with Apple the worst offender - so a Wi-Fi server can be very handy. None are fully baked yet and often have limitations on the file types they'll stream to a tablet, so they're currently best for people willing to dig into documentation.
Seagate, Buffalo and LaCie are current leaders and all offer wireless servers in the $100-$250 range. If you don't like fiddling with gadgets to get them to work, wait until next year when they should be easier to use.
Online backup Few remember to back up their data and when a drive fails - and they ALL do, even SSDs - it can be tragic. Online services are set and forget easy, although if you have hundreds of gigabytes to store it can take days or weeks to upload. I like Backblaze - very simple - and Crashplan - more control.
The Storage Bits take The storage market has lots of selection and lower prices than last year. And everybody needs more, so splurge!
Comments welcome, of course. Disclosure: I've done business with or been given products by a couple of the vendors mentioned above. Mostly I buy products just like you do. Readers: do you have any favorite storage products we should know about?