I just had the whole thing installed I can answer

1) Is a separate Cat5 cable run into my house from the outside box to each TV set top box inside? ( I have four )
Only 1 cat5 drop is done to the router they will supply. The boxes do not get ethernet connections. A black box is then uplinked to the router, from this black box is a COAX cable run into the splitter that feeds all your STB (set top boxes). They are creating a coax peer to peer network for the STB's in the house. All information for video on demand and the guide is done through "data" on the coax cables.
2) Do they run another line from my Fios internet router to the TV ? or is it a totally separate unit?
Ya they run a cat5 cable to the black box for FIOS TV suuport, see above. No ethernet gets run to TV. They use the existing FIOS internet router you already have.
3) I have been told that they will NOT fish network cables down walls. Please tell me they don't plan to use any of my existing coax cable like the satellite guys did!
Thats not really true. They dropped 1 coax cable (which they will do where your router is) and dropped 1 ethernet cable, and fished it. If not just offer them a case of beer and they will do it

4) I would like to have a WIRED home network system connecting several rooms. How can I do this and integrate my Fios TV and internet service?
They typically will give (gave) a wireless router free. But, you can have a wired network if you want, you will need a patch panel installed somewhere and have it wired to the router. Wireless is probably easier and cheaper.
FIOS TV only uses the network through the coax already in your house for its on demand stuff and guide.