How is the person selected? How far in advance is the selection process made? When a department makes an offer to have a speaker come, how often is the offer rejected? And what happens if the offer is rejected?
It varies tremendously, based on the type of talk.
To a first approximation, anyone can invite a speaker if they have grant funding to pay for the travel costs (or if there are no costs). The limiting factor is getting an audience - it's embarrassing for everyone if few people show up - so this typically happens only if it's clear there will be real interest in a talk.
Departments in research universities typically have a number of ongoing seminar series, and often a departmental colloquium as well. There will be one or more organizers for each of these, who invite speakers and introduce them before the talks. How the organizers are chosen varies: sometimes they are volunteers, sometimes they are appointed by the chair, and sometimes they got a grant that's paying for everything. The organizers can then ask whoever they want to speak, although they often solicit suggestions from other department members.
There may also be special distinguished visiting positions or lecture series. These are quite a bit more prestigious and speaker selections are often made by a special committee.
How far in advance invitations are made can vary: typically many months in advance for a prestigious lecture series, but a seminar invitation may have less advance notice.
As for how often an invitation is turned down, it's rare for someone to express a lack of interest in principle, but it's common for them to be too busy or for it to be impossible to arrange a mutually agreeable date. I often suggest that someone should come speak sometime in a seminar I organize. Sometimes they immediately start arranging a date, sometimes they defer it to another time but eventually come, and sometimes it never works out, but even in that case it's never certain it won't happen someday. If a speaker can't make it, it's no big deal: you just invite someone else.
Let me add to the answer above. If you're interested in having a researcher come speak at your department, the seminar organizers are often open to suggestions, especially if the potential speaker isn't looking for much in the way of travel costs. Conversely, if you're interested in speaking in a seminar, it can be completely appropriate to invite yourself. This often works better when you've at least met the organizer of the seminar where you'd like to speak; however, you definitely don't need to know him or her well. On more than one occasion I invited myself to speak somewhere. The two or three times I can think of off the top of my head, the organizer was happy to have me. (I think it helped that I didn't ask for any travel reimbursement.) And in each case, I enjoyed my trip and I think my audience enjoyed my talk.