It's not enough of a project to document here. There are tons of sites on the web that describe it and any basic home maintenance book will too.
This is a simple one because I only have to run each wire about 15 feet from the source, up to the room direcly above the source. Cut a hole in the wall for the old work box, drill down to the basement, run the lines along the foundation sill, up through the new hole, into old work box, connect cat6 jack(s), rg6 lines, and I'm good.
The primary caveat is not to hit anything in the wall while you're cutting. There is only one outlet on that wall and I've traced the wire so it appears to be completely out of the way. Still, watch what you're cutting while you're in there and be damn sure all proximal circuits are cut at the breaker.
I'm going to go with a cat6 and a phone line. This one is easy enough that I can just swap out the phone line for another cat6 later if I want and I don't have the cash to put in a real patch panel yet. All phone lines go to the phone source now and all cat6 go to a hub I have mounted next to the electrical panel.
And as for putting a NIC in the Tivo, I don't really have need of it now. My main DirecTivo has a NIC in it but I haven't even connected it to the network in well over a year.