tldr: The only tax involved is gift tax, and there is a rather large gift tax exemption (an individual can give more than $11,180,000 in gifts during their lifetime before taxes get involved), so in the vast majority of cases no tax is involved.
Does the person the stock is coming from have to pay any taxes on their gain at the time of transfer?
In most cases, the size of the gift would be the cost basis of the stock involved. The exception is stocks received due to inheritance, in which case the size of the gift would be the fair market value on the day of transfer.
If the size of the gift fell below the gift reporting rules ($15,000 per giftee per year), it would not need to be reported. If it is above that, it would need to be reported, but until the full value of the gift tax exemption had been reached ($11,180,000 in lifetime gifts), no actual tax would be incurred.
For married couples, those numbers are essentially doubled. A married couple can give up to $60,000 to another married couple (either member of the giving couple giving $15,000 to each member of the receiving couple) per year without having to report it.
There are specific rules for stepping up the cost basis if the gift tax is actually getting paid.
For the person receiving, does the basis transfer or is the basis for the person receiving set on the date of the transfer?
The cost basis stays the same, unless the stock is inherited, in which case the basis is the fair market value on the day of transfer.
What would be the difference if the stock was sold and just the proceeds transferred?
The giver would be paying capital gains on the stock sale, and then giving the money. Gifting the stock instead obviates the need for the giver to pay any capital gains.
Other than being married, would there be any relationship where the rules would be different (parent/child where one is a minor when the stock was bought, siblings, etc)?
The only exception is spouses. Tax law does not take into account buying something for someone else as any form of official ownership.
https://www.irs.gov/pub/irs-pdf/i709.pdf (specifically about the gift tax exemption rules)