In video editing, how to fade scenes out, with next starting immediately after?
How-to

To acheive this effect, use the Gamma Cross Effect Strip. 


To begin overlap your videos, so it looks like this(it does not matter which channel the videos are on).
Next, select which video you want to fade out with the RMB(usually the first video). Then, using SHIFT RMB select the next video. 
Finally press SHIFT A and navigate to Effect Strips... and click on Gamma Cross. The cross duration should be the length of the overlapping videos. You cannot change the length of the gamma cross directly, you must increase or decrease how much the videos overlap. 


Reasoning

If the videos are directly next to each other, but not overlapping, you can't have the second video start right away because how can the second video start if the first video is still going and they are not overlapping?
 
Reference : https://www.blender.org/manual/editors/sequencer/strips/types/effects/cross.html

Reference Video: https://www.youtube.com/watch?v=T_PRXTZoHtI&amp;list=PLjyuVPBuorqIhlqZtoIvnAVQ3x18sNev4&amp;index=14 

Audio Reference Video: https://www.youtube.com/watch?v=beWj_mw0M-I

AudioAs for the audio do as RobinsSea suggested in his answer, insert keyframes along the timeline concerning the audio level of the videos. To do this select the audio track and navigate to the properties panel "N". Make sure your timeline is where you want the audio to begin fading out! Over in the properties panel go to the volume area and hover your mouse over the volume. Then press "i" to insert keyframe. Do the same to complete the fade out, just set the volume to 0 and the timeline where you wish to end.

Happy Blendering!