I cold-emailed him and just asked, and he said yes. Turns out he had already heard good things about the show, so he was inclined to accept my invitation.
Get ready to hate me - getting guests for my show has been pretty easy, in general. Nobody has ever refused to be on the show, although a number of people have had problematic schedules.
Actually, wait - one person declined my invitation, but that was due to being uncomfortable doing an interview in English (it was their second language).
I hear some podcast hosts express difficulty in getting guests, but I'm going to keep riding the "just e-mail and ask" bus until the wheels fall off! Nathan was a great get and a cool guy and I'm really glad I was able to share his story with my listeners. :)