Best companies to work for (see footnote) are the ones that treat their former employees as alumni, rather than as traitors. I was extremely nervous during my last job transition, given I've only stayed there for a year and likely caused them headache during my initial recruitment, dealing with multiple offers and many sleepless nights.
To my surprise, they not only took me out for a going away lunch, they even paid for it. While a job transition is stressful, professional treatment at exit does re-inforce goodwill (which is already earned: kind treatment on the way out, implies kind treatment while I worked there). I still endorse their products (on technical merits) and talk to my former coworkers there.
At the exit interview with my then-manager (who, by the way is great), I expressed my regrets at leaving so soon. While he was understandably upset, he mentioned that while short stints will close some doors, loyalty isn't an end to itself; he found that many candidates that stayed 15+ year for most of their career weren't very impressive during interviews.
Obviously, I think there are exceptions to this rule: if you're lucky to join a place with a strong hacker culture (e.g., Google, PARC, Bell Labs, Sun, Yahoo, IBM, Microsoft etc...) at the right time and on the right team, there's good chance you will be able to do rewarding work for a long time. However, the name alone is never a guarantee (there are plenty of non-interesting but business-crucial projects at these companies e.g., not everyone can work on Search or GMail at Google), nor do these companies last forever (as Sun's decay exemplified).
On the other hand, if you systematically stay for less than a year at various jobs (particularly at companies with longer development cycles e.g., bigger companies, or start-ups still in product-development phase), you might never get a chance to complete (or even undertake) challenging and rewarding projects.
This can lead to a vicious cycle: you will your work is always unrewarding (as you'll never stay long enough to either reap the rewards of the work or even receive challenging projects in the first place) tempting you to change jobs again. At the same time doors begin to close: the stigma of "job hopping" (Silicon Valley tech companies can understand 4 jobs in 5 years, 10 jobs in 10 years is a more serious red flag), lack of age-appropriate experience, confidence and leadership skills that come from finishing projects and shipping products, and "burned bridges" due to upset coworkers (who else would serve as your references?). In the end, you're ending up with progressively worse options.
There's a balance. If you're happy with the job, are learning and find the work itself rewarding, don't actively "go on the market". Don't leave before you get a chance to learn anything. However, once you feel you're either no longer learning anything new, or have not learned anything new at all after a year, do something. As I've mentioned in another comment, bring it up with leads/management first (something I regret not having done twice in my career): a manager will likely not realize you're underused and unhappy (provided you act in a professional manner and still do the job asked of you), many companies are open to internal transfers (most notably, but not exclusively, Google); furthermore this avoids the ambiguity of counter-offer (are they doing this because you've "put a gun to their head" and simply need you to finish a project, or are they genuinely interested in your success?) and stigma/un-professionalism of accepting one.
Choose your jobs carefully: is the focus of the company aligned with your interests, is the product valuable to you (e.g., if you don't understand the value of recreational social networking, Facebook -- otherwise a great company -- may not be a good place to work), will I be able to keep up with the greater technology curve in my specialty area, will I be able to learn new concepts (and not just new technologies), is the engineering team strong and influential? Don't optimize prematurely for salary and title (if your title is too senior, you might not receive the needed amount of mentoring or the chance to be a protege), don't guess whether or not you'll get rich from the stock options (if you're actually great at guessing the value of stock, consider a career as an investor), while you should know how long the company will be able to pay you (given their current burn rate) don't stress over current or rumored layoffs (I've declined two very interesting offers in Summer/Fall 2008 due to recent/possible layoffs, I grew to regret it. Is your most interesting offer from Yahoo? Then take it and ignore that Techcrunch and Gawker say!
Don't just shop your resume around, focus on a few positions that interest you and apply just to them. Don't limit yourself only to start-ups or only to Fortune-500 companies; don't just limit yourself only to the two extremes, with the exclusion of medium sized companies which often have the benefits of both start-ups and big companies, pay more fairly than both and give equity that may not be life changing, but is actually worth something (I'm biased, as I work at one such company). There are teams within big companies that exhibit the positive aspects of a start-up (2-3 people working on a project, each owning a significant chunk), there are start-ups which exhibit the negative aspects of big companies (outdated technology, mediocre technical teams, all technical decisions being made by non-technical management). In some cases, start-ups live up more or just as much to big company stereotypes than do advanced technology companies: open floor plans are almost universal (big companies go for cubes or offices shared by developers), use of Blub languages, non-technical professional CEOs running the show, projects generally consisting of putting a UI on top of buggy code written by somebody else (e.g., API mash-ups, Facebook apps, CRUD applications). The ones that stand out from that (at least in some respect) are the ones likely to be great (compare this job posting http://groups.google.com/group/mi.jobs/msg/d81b6c1fa8f361fc?... with the average "2+ years of RoR, Flash, HTML, Javascript and MySQL" one).
Ask "will this job be valuable to me even if I don't stay there for a long time?", as chances are one that's valuable for two years is also valuable for five. If it fails after the two years, but the environment stimulated you to do great work, you'll not only walk away with knowledge but with respect of peers who will be ready to refer you to other jobs. Accept that you will make mistakes, be ready to (carefully and patiently) correct them and learn from them.
(footnote) Since the original article was prompted by Jason Calacanis' reaction to an employee leaving Mahalo -- his start-up -- to join Yahoo, I should note (to those in the Web 2.0 "reality distortion field") Yahoo still counts as a best place to work amongst the Fortune 500 (my first job out of college and also my longest stint as a full time employee) and Mahalo doesn't. Somebody leaving a hyped company to join one that is going through a difficult time to do work they find meaningful and interesting is someone I'd like to hire even if they have a few 11 month stints on their resume.