I know that under FAR Part 135, specific approval is required for an RNAV SID/STAR (given via an OpSpec), but what about Part 91? Does the aircraft/pilot have to be approved, and if so how is the approval obtained?
The best answer I can give is generally, no.
In relatively few cases – for aircraft operated under Part 91 Subpart K, which applies to fractional ownership like Netjets – the operator must possess an Mspec, which would be applied for at the local FSDO. I'm not sure what that process looks like, but the FAA's Commercial Operations Branch has some good information on that front.
For all other Part 91 operations the aircraft simply needs to be appropriately equipped.