Just as we all expected, ("Certainly the next logical step would be for these videos to be shown in Google Maps."), Google has enabled videos in the Google local maps section. For some time now, Youtube videos have been available within Google Earth. So, it only makes sense to extend this functionality further.
They have not yet added a way to search for videos exclusively within Google Maps, but you may stumble upon a video hear and there within the map results. If you stumble upon a result that has a video, you will see the video within the "photos & videos" tab of the map bubble that appears when you click on a listing.
Currently, videos can only be submitted by local businesses that list their business within the Google local product. As for consumers, at this point, they can only watch. To add or associate a video with the maps product, simply upload your video to Youtube, make certain that you specify the proper geo-location of the video upon upload, and then go to the Google local business center to associate your video with your maps listing.