For Sitecore Azure (up to 8.1) how are the hostnames configured for Azure PaaS CD environments? Is this something which happens automatically based on settings found in Sitecore.config/Web.config?
You need to configure the hostnames in the portal (or via PowerShell) first. This will involve a DNS validation step so you will need access to your DNS provider as well.
You only need hostnames in the Sitecore Config if your system needs to differentiate site content between several domain names. If it's just the one, you only need to configure the Azure website.
PS Azure Website-grade PaaS is only officially supported from 8.2.1 Be careful when running multiple instances as there are Sitecore components that use the file system for storage and Azure PaaS had a shared filesystem across instances.