The easiest thing to do is move the router around to get the best signal bounce down the hallways and up the stairs. The router connects to the modem with an ethernet cable and you can buy a longer cable to mount it where you need it to get the best signal.
There are highgain antennas that you can buy to boost the signal as well.
1. Change the wireless channel on the router, you might be getting congestion on the current channel.
2. Cordless phones are common causes of interference and weak signals. Try turning them all off (remove batteries and unplug base stations).
3. If the router has external antennas, play with the orientation. Little changes here can make a HUGE difference. Your typical dipole antenna (looks like a stubby stick) radiates out from the sides of antenna in a doughnut shape, so don't point the antenna where you want signal, point it 90 degrees away.
4. Move the router up to head height and away for any walls if you can.
5. Get rid of any other wireless devices in the immediate area. If you have wireles mice or keyboards, see if the signal improves if you turn them off.
6. Depending on model, you can sometimes get a wireless access point to act as a repeater, placing it half way between the router and the target use area. Combination like the Linksys WRT54G and WAP54G works very well.
7. If the router has an external antenna, the manufacturer may sell replacement high gain antennas.
8. If you're andventurous and your router is supported by third party firmware like dd-wrt, these firmwares will sometimes allow you to increase the power output of your router so you can get a stronger signal to the wireless devices.
EG wrote: That's a good idea but you do lose most of the router's omni-directionality ability.
That is why I did put the condition of "if the router is at one end of your house" thinking a directional pattern would increase signal strength within the house. I now realize that condition would not identify all the uses the OP might require (e.g. WIFI access outside the house). As an experiment, it is a cheap way of determining if a few (1 or 2) db increase in signal strength would help. It then might make sense to invest real $$ in a high gain omni-directional antenna.