Thanks for the tip.
I found one more long scrap of CAT5 in my wiring box last night.
I cut up a DC-ROM audio cable, to get the 4-pin sockets from the ends. These are perfect for both the DSB1820 and the DHT11, allowing me to swap out sensors if need be, without having to solder more.
I put both connectors onto a small piece of perfboard (I still have to hot-glue them in place or something), and wired them to the end of the cable. A little white electrical tape will make it less noticeable once it is inside the vent (of course I can't tape over the sensors themselves).
I hope to have time this weekend to pull the wire up through the duct, and hang it from the inside of the return grille. Then, I have to wire it up to the arduino and test it.
I'm still trying to figure out the best way to interface all this with the Arduino.
I have a prototyping shield, that already has my status LEDs, and all the needed resistors for the inputs and outputs. I have a set of 4 wires that go to a terminal strip where I connect the wires from the furnace/thermostat interface. I have another set of wires going to a second terminal strip, where I have the wires from most of the DS18B20 and DS18S20 sensors coming in. I also have wires going from there to a small breadboard where I have two more DS18B20's. It is a good place to add stuff for testing, without disturbing the screw terminals on the terminal strip. Another set of jumpers temporarily goes from the Arduino to that same breadboard for the DHT11 at the moment. I just have to pull the shield off the Arduino, and solder in a more permanent set of interface wires for the DHT11 (I might add a second data channel wire while I'm at it, for future expansion).
Eventually, I'll replace the Arduino Mega with the Uno that I bought. I have a few of the "Really Useful Boxes" (from Office Depot), which are the right size to make an easy enclosure. I'm not sure how to do the external connections, though. I want to be able to disconnect the wires coming in relatively easily, if I need to take the system apart to move it or make changes. I was thinking of attaching a screw terminal strip to the box, and connecting everything that way. I can join the DS18B20/DS18S20 wires together at a point closer to where they diverge to go all over the house, and have that be a bit neater, too.