There are several steps in the process and the answers above have hit on some of the steps. But here's the the whole enchilada in a nutshell. The first thing to remember is don't alter any of the original files or sounds contained in your pak0.pak file!!!!
If you have your own mod folder, create an empty folder in there called "sound". So you should have sierra/half-life/mymod/sound.
I used pak explorer to extract the sounds folder in the half-life/valve/pak0.pak file. Grab a copy of the sentences.txt file from there and place it in your mymod/sound folder.
I am assuming you have some custom sounds already that you want to use. Create another folder in your mymod/sound directory to hold your custom sounds. Now you have mymod/sound/custom full of your new sounds. Put You'll need to convert them to 8 bit mono wav files. I used Goldwave in a batch mode to convert the whole folder at once.
Then in mymod/sound/sentences.txt, look for barneys or scientist sentences. Find the ones you want to alter and change the directory and filename so it points to your new custom sound folder and filename. Like Andy said, look at the folders in HLywood and you'll see what I'm talking about here. For the monster sounds I did it differently because they don't have sentences. Worldcraft dude explained that method above, just remember to convert any custom sound to 8 bit mono wav format. Man, I feel like I just wrote a tutorial!