How are PID's generated?

As wikipedia says,

Under Unix, process IDs are usually allocated on a sequential basis, beginning at 0 and rising to a maximum value which varies from system to system. Once this limit is reached, allocation restarts at zero and again increases. However, for this and subsequent passes any PIDs still assigned to processes are skipped.

so it's really a very simple policy for "generation", just increment a counter, and "recycling", just wrap the number around at a max value and keep incrementing until you find a number that was assigned to a process that has finished and has been removed from the process table.

Some Unix implementations such as AIX use a policy that's less simple, see e.g. this FAQ.

It varies.

Most systems simply keep a count of the last PID generated, add one (wrapping at a maximum number such as 65535 or a bit smaller - often the wrap occurs at 65000 or even 60000), and check that the number is not currently in use (repeating if the PID is still in use - so PID 1, the kernel, is still there and doesn't get 'reissued').

Other security minded systems generate a number at random and check that it is not in use.

At any given time, it is guaranteed that all PID numbers are unique.

As to the recycling part of the question, one thing to keep in mind is that a pid does not become available as soon as the process with that pid terminates. The pid does not become available until the parent of that process collects the termination status of its child via some form of the wait() system call. A child that is terminated but whose parent has not issued a wait is called a zombie and will usually show up in a ps as defunct. It is possible for an ill-behaved parent to starve the system of pids if it launches children and does not wait() for them.

If the parent of a process dies before it collects the status of a child, that is ok. The child is inherited by init who will make sure a wait() is issued and the pid is recycled.