Changing Notification Sound in Yosemite/El Capitan
Yosemite Instructions:

Convert the sound you want to use to .caf using afconvert:

afconvert -f caff -d LEI16@22050 input_file output.caf

Go to 
/System/Library/PrivateFrameworks/ToneLibrary.framework/Versions/A/Resources/AlertTones/Modern

Since I wasn't sure just adding the new .caf file to this folder would work, I made a copy (backup) of sms_alert_note.caf and then replaced sms_alert_note.caf with the new file. Since it doesn't work at first (I think you have to somehow reload the framework), I restarted. After restarting the default "Note" sound was replaced by my own sound.

EDIT: El Capitan (dirty) solution (without disabling SIP)

First: prepare the .caf file as instructed above using afconvert.
Reboot your Mac into recovery mode (hold cmd+R while booting). Open the Terminal from the utilities menu and type diskutil list to get a list of the connected disks. Make a note of the name of the disk containing the boot volume

/dev/disk0 (internal, physical):
   #:                       TYPE NAME                    SIZE       IDENTIFIER
   0:      GUID_partition_scheme                        *1.0 TB     disk0
   1:                        EFI EFI                     209.7 MB   disk0s1
   2:          Apple_CoreStorage Macintosh HD           1.0 TB     disk0s2
   3:                 Apple_Boot Recovery HD             784.2 MB   disk0s3`

/dev/disk1 (internal, virtual):
   #:                       TYPE NAME                    SIZE       IDENTIFIER
   0:                  Apple_HFS Macintosh HD          +1.0 TB     disk1
                                 Logical Volume on disk0s2
                                 8D6D5ACA-6AFF-4F53-9E61-2D83A2536501
                                 Unencrypted


In this case the boot disk is disk0 containing the boot volume "Macintosh HD. Now type diskutil mountDisk disk0 to mount the disk (replace disk0 with whatever your disk name actually was).

Your startup disk should now be mounted in /Volumes/Macintosh HD(or whatever your boot volume's name is), cd to that location: cd /Volumes/Macintosh\ HD and type chroot.

Now you have full access to your boot volume without having to deal with SIP.

Go to the folder where alert sounds are stored
    cd /System/Library/PrivateFrameworks/ToneLibrary.framework/Versions/A/Resources/AlertTones/Modern

Make a backup of the original sound you want to replace (I'm replacing the default 'note' sound)
    mv sms_alert_note.caf sms_alert_note.caf.bak
Copy the .caf file you created earlier to the folder:
    cp /path/to/new/notification.caf ./sms_alert_note.caf
(note: simply adding a new file won't work as it won't be recognized by Messages, you'll have to replace one of the existing files)

Reboot. You will now be able to use your custom sound by selecting the name of the notification you replaced in the AlertTones/Modern folder in Messages -> Preferences -> Message Received Sound. If you replaced sms_alert_note.caf this will be "Note (Default)".

I don't expect this to hold through system updates, but it might if the AlertTones folder is not modified.