First, make sure cookies are enabled in the user's browser.
If that doesn't fix the problem, it may be that the user's ISP implements a rotating proxy server. This causes the user's effective IP address (the address which the Bugzilla server perceives him coming from) to change periodically. Since Bugzilla cookies are tied to a specific IP address, each time the effective address changes, the user will have to log in again.
If you are using 2.18 (or later), there is a parameter called "loginnetmask", which you can use to set the number of bits of the user's IP address to require to be matched when authenticating the cookies. If you set this to something less than 32, then the user will be given a checkbox for "Restrict this login to my IP address" on the login screen, which defaults to checked. If they leave the box checked, Bugzilla will behave the same as it did before, requiring an exact match on their IP address to remain logged in. If they uncheck the box, then only the left side of their IP address (up to the number of bits you specified in the parameter) has to match to remain logged in.