Hey man,
The cheapest solution I could think of would be drilling holes in our house and running cable all over the place, tieing it down with plastic wire supports. But I don't think you want to do that.
The next best solution I can give you is to buy a wireless router. Now right now you're probably thinking, "I just said I didn't want to do that." Hear me out. When you drop by your local Best Buy, Future Shop, what have you, and you run over to the networking section, you are going to see alot of networking equipment. Now I know that today's wireless routers can come with wired ports. I know this because I have a DLink at home with wireless and wired ports.
So if you think about it, swap out your wired router for a wireless router, plug in your wired computers to the wireless router, grab a wireless receiver for your computer, slap that into your system, and voila! Instant upstairs network access. Don't forget to password protect your wireless signal.
I'm sure others would agree that this is the best way. However, I don't know everything so you can wait for some more replies to this topic to see if anyone has some better ideas. But as far as mine go, it's a face-off between holes in the house or wireless access. Hope this helps.
Cheers:)