If you're going to be looking at EPA certified stoves, and as one poster has already you mentioned, you should be because it's the smartest way to go. They're 1/3 more efficient (on average) than a regular old box stove, therefore 1/3 less wood burned and pretty much 1/3 less work all the way around. Don't get too hung up on published efficiencies and particulate numbers of the different stoves, last I knew no two stove manufacturers are arriving at those numbers in same fashion, there's no standard methodology to calculate those numbers. It's really how big a stove you need and whether or not you like the looks of it (this is where you want to involve the Mrs.). Don't be afraid to go a little too big on the stove, you can always cut back the air flow, burn a smaller charge of wood, or burn wood with less btu content with bigger stove. But when it gets really cold, you'll have to fire the heck of the smaller stove to keep up with heat loss of the house, if you'll be able to at all. One other thing to consider if whether or not you want a catalytic stove or non-catalytic stove. If you're the type of person who likes to tweak to get every last bit of usable btu's out of the wood, then the catalytic stove is for you. If you're a "set it and forget it" type, then go with the non-cat stove. After the catalytic combustor starts to degrade and the efficiency starts to fall off, the efficiency of the two type of stoves averages out over the life time of them, or so I have heard. One advantage of the catalytic stoves is that you can get a lower and slower burn out of them without smoldering. In order of lowest to highest cost of construction it goes welded steel, cast iron and then soap stone. There is really no performance difference between the types of wood stove construction, what do you like the looks of and how much do you want to spend?
You really need a 6" round (or a cross sectional area that works out to be the same) stainless steel chimney liner, insulated liners are very good idea but not necessary, running from the stove all the way up to very top of your house to get good performance. When your stove is performing well, it isn't the stove that is performing, it's the chimney that is doing the performing. The chimney is most important part of the system and that cannot be understated. A conversation with a chimney sweep may be a good first step, because without good draft, wood heating just isn't fun.