Varies from company to company (or even local offices), but it's usually around $15-$20 per box, or about twice what a regular cable box will be. Some may charge a separate service fee from the box fee.
Cable company DVRs are usually self-contained, so you usually need one per TV. But other DVRish solutions, like a HTPC with media extenders, or Moxi's older DVR with Moxi Mates (and I assume their newer home house solution) can use one central DVR to do the recording and then send the signal to other TVs. Something needs to be at each TV to pick up the signal sent from the main DVR, though.