I would like to explore Doubtful Sound and looking on Google maps it doesn't look particularly accessible, so what are my options?
The best way is to go with a tour as the trip requires crossing Lake Manapouri and there's an hour long coach trip to Deep Cove. For more information see the NZ Fiordland webpage.
There are a couple of tour options, including overnight stays on a boat, a couple of companies:
As far as I remember the overnight stay options are quite popular so you'll need to book in advance.