What is the process through which a department chooses to invite someone to make a talk at the department?
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.