Steve Espinosa has noted on his blog that Maps is now supporting the option of adding a video to your business record in the Local Business Center. The feature is now live.
The process of adding a video is similar to adding a photo. The business is allowed to display up to 5 videos in their Maps record and once they are added in the LBC, they show up immediately in the Map record. Interestingly they display before the photos.
Maps Record Screenshot:
Local Business Center Add Video Screenshot: