In early alpha I remember Minecraft videos showing slimes deep underground. I think you would attack them then they split into several smaller slimes. But I've never found a slime for myself. In what conditions can you find slimes? Are they definitely still in Minecraft?
Edit: As of Minecraft 1.5 or so, Slime spawning has changed yet again. Right now, Slimes will only spawn in certain chunks of your map, depending on the map's seed. There are tools online such as this one that let you input your seed, and it will output the chunks of your map that will spawn Slimes.
Slimes spawn within 16 blocks of bedrock, in any light conditions. I think they were removed in the 1.2 Beta, but it is confirmed that they have returned in 1.2_01.
Slimes spawned fairly frequently back in Alpha, but I believe Notch reduced the spawn rates by quite a bit since then. The 1.3 update increased the slime's spawn rate yet again.
The fact is that slimes now spawns naturally at night (technically light level < 8) in swamp biomes ("Swampland" in debug screen) with y-coordinates ranging from 51 to 69. This feature is added in 12w40a development snapshot or 1.4.2 (Pretty Scary Update) release, making them much easier to be found.
Slimes also spawn below y-coordinates of 40 in specific chunks. Minecraft Wiki has a formula on the slime spawning mechanism and there are numerous tools to find slime-spawning chunks, however since it is subjected to change, it may be far easier and better to find slimes by simply look for swamp biomes on the ground.
As of the 1.3_01 update, slimes have a higher spawn rate, spawn in ANY light conditions, and on ANY mode. If you put it on peaceful, though, only small slimes will spawn.
Slimes spawn in the bottom 16 blocks of the map, but only in 10% of chunks.
Here is an online tool to determine which chunks are capable of spawning slimes: http://mcslimes.appspot.com/
If you hear a distinct, repeatedly clicking sound, you're very close.
You can find slimes near bedrock, but only in 10% of chunks. If you want to find slimes more easily than digging around forever, find a swamp biome--about y level 64 they spawn naturally at night.
Go get a bunch of TNT and blow a hole to bedrock. Then, make the hole wider. Go do something else for a Minecraft day or two, and come back to the cavern. You'll find many slimes there.
dig a hole down to layer 4 and make a 4 high by 1 long room. Then dig three blocks straight ahead. Once you have done that then dig 50 blocks on either side, once you have done that dig out about 20-30 blocks deep. By the end of all this you should have 4 block high room that is 100 blocks wide and 20-30 blocks long. Then place tons of torches to totally flood the area in light to stop other mobs spawning. Finally after all this work all you have to do now is return to the surface and wait. Give it a couple of minecraft days and go back down and you should see a fair few slimes. Kill and enjoy all the slime balls you have collected