One of the irritating problems with Linux in general is Bluetooth. Below are the steps I had to follow to pair and use a Creative WP-300 Bluetooth headphones with Kubuntu 16.04. The procedure should be similar for any Bluetooth headphones or speaker and with any other variant of Ubuntu.
Make sure that your computer has a Bluetooth adapter and it is working. Do not just assume there is an adapter and its working in Linux! You should be able to see a Bluetooth icon in the system panel or system tray. In the Bluetooth settings you should be able to see the adapter.
Power on your Bluetooth headphones or speaker and put it into pairing mode. Refer to its documentation if you do not know how to do this.
Go to the Bluetooth settings in Linux and try to find device and once the device is listed, pair with it and connect to it.
Go to the audio settings and you should be able to see the Bluetooth device listed there. If it is not there, you might need to restart Linux. I know it is crazy, I had to do this, since no other solution offered online worked for me!
If your device is listed in audio settings then try to play some music or video and see if it plays in the device. Most probably, it will still play on the default speaker of your computer! Go to System Settings → Multimedia → Audio and Video → Device Preference → Audio Playback. Your Bluetooth device must be listed here. Grab it and move it above the built-in audio device. This tells Linux to use this as the default audio output.
Now you should be able to playback audio to your Bluetooth device 👍