Basically just get a smallish stove. The amount of heat is directly proportional to the amount of wood and air you feed it.
If possible, get a newer style stove that re-burns the combustion gasses. Far more efficient than the old straight shot up the flue.
I wouldn't get too small of a stove for full time use. You want to be able to stuff decent size 16-20" long logs in it and not have to turn your wood pile into glorified kindling to fit in the stove.
And yes a good insulated fire proof floor, back wall and triple lined flue pipe are necessities. If not worried about aesthetics, plain old durarock works great for floors and backstops.