Decision #1: Capacity
The pivotal decision you'll need to make is how much capacity you're looking for. This decision isn't just a question of how much money you want to spend. It also will determine whether you'll be looking for a RAID-capable NAS (I'll get to RAID shortly). But this decision is complicated by the fact that the decision points continue to move.
Until recently, 500 GB was the crossover point between single and multiple-drive NASes. If you were looking for more capacity than that, you needed to move to a RAID NAS. But 750 GB drives are now here and available in the single-drive Buffalo LinkStation Live (HS-DH750GL) and Pro (LS750GL) models. The Hitachi Deskstar 7K1000 is the first 1 TB (!) hard drive, and Samsung and Seagate have also announced Terabyte drives. But none have made it into NASes yet.
So, aside from the Buffalo products, if you're looking for more than 500 GB of storage, you'll need to look at RAID NASes, which opens up a different set of decisions you'll need to make.
But even if you opt for a RAID NAS, note that currently (summer 2007) many are limited to 2 TB of storage. However, some manufacturers have released firmware updates to raise the storage limit to 3 and even 4 TB. So check specs carefully before you buy.
NOTE:While you might be tempted to think that you can push this single-drive crossover point by attaching an external USB drive... don't! External USB-based storage is usually treated as a separate share that can't be combined with internal storage.
The external drive must also often frequently be formatted with FAT32 to even be recognized and some NASes won't recognize multiple partitions on the USB drive.
Decision #2: Features
With the "how big?" decision made, you now can narrow your choices by looking for features to support the functions you desire. There are many ways to come at this, but I group desired functions into five categories: Backup; Media Serving; Access Control; Network Filesystems; and Other Services.
There are actually two kinds of backup to consider in your prospective NAS: network client backup and backup of the NAS itself.
Backing up network clients is usually handled by a software utility bundled with the NAS that needs to be installed on each client that you want to back up. Examples of this are the Memeo backup bundled with Buffalo NASes and EMC's Retrospect Express that comes with some Iomega products such as the StorCenter Pro 150d.
Infrant also bundles Retrospect Express with its NV+ desktop and 1100 rackmount NASes [reviewed here]. And in a pleasant departure from the norm, i.e. Windows-only bundled applications, both products include 5 licenses for both Windows and Mac OS clients. All of Infrant's ReadyNAS line also have a built-in backup function that can backup any network share. So this function can be used to backup client files without running an application in the client!
Sometimes the bundled backup program is a limited-time or otherwise crippled demo version. And sometimes, as with the Retrospect Express case mentioned above, you get a limited number of client licenses. So I don't recommend making a NAS decision based on the bundled backup solution unless you're already familiar with the application and know that it will meet your backup needs.
The second backup function—NAS backup—is easily overlooked, but probably more important than the first. NASes provide a handy and jumbo-sized place to stash all the pieces of your digital life; all of which could be gone in a matter of seconds without a proper backup. And as the commenters in my Smart SOHOs Don't Do RAID article pointed out, the extra data security provided by RAID is not a substitite for backup.
I recommend buying only NASes that have built-in capability to do scheduled backups, preferably to both local, USB-attached drives and networked shares. And whether you do your backup to a USB or networked drive, set up the backup feature when you install your NAS, and monitor / test it at least once a week to ensure that backups are being done properly.