A few times per decade.
My colo'd server (RH7.x) was up over 4 years when the colo operator had to do a physical move to a new facility.
My home system (SL4) pretty much reboots only for extended power outages or major updates with kernel changes I really, really want.
The rest of the family's systems (FC9) reboot once or twice a year when a new Fedora release is installed.
At work (CentOS4 or SL4) the average system stays up 6 month to 18 months between reboots, although we have some desktops that reboot a few times a year. Infrastructure systems (from RH9 to SL5.2) average a year up. Windows infrastructure systems stay up from 6 months to 2 years, but they each run one service (plus whatever is required for that service) and remain lightly loaded (by design). We have no Windows desktops, and Windows laptops are rebooted regularly as one might expect.