SSL had been around for 6 years already, credit card transactions were quite common, especially with known, reputable hosts (Network Solutions can be safely be assumed to have qualified at the time)
But the linked article specifically mentions an HTTPS link.
People who used mail orders before the internet might remember that the options included sending a cheque along with the order form or filling in your credit card details on the order form (that's a paper form that you send in the post), and I think that this is still the case. So I don't think that average people really saw sending card details online any differently. I even remember being asked for my card details by email!
But, yeah, paying on-line with credit cards was absolutely a thing in 1999.
Presumably Network Solutions was trusted by this customer of theirs.
There were thousands of online shops at the time, selling everything that Amazon sells today, and it was common to purchase from them using CC or PayPal.
I'm not sure it's even so much that PayPal "popularized" online payments as it somewhat democratized them. When I had a small side software business in the early to mid-90s, it wasn't easy/cheap to get setup with a merchant credit card. Mostly, people mailed me checks although at some point I struck a deal with a local BBS operator/reseller for him to take payments for me when necessary.