The making of AMVs is legal, since such a use falls under fair use doctrines. Distribution of AMVs, due to their contents, is an area of legal dispute.
AMVs inherently consist entirely of copyrighted and unlicensed material, including entire songs and substantial portions of television series or motion pictures. Thus, legal concerns vary depending on several factors. As a general rule of thumb AMVs can be seen as illegal in the de jure sense, however, legalities concerning copyrights are subject to variation based on the copyright holders' consent. Many AMVs have so far been viewed as acceptable under Fair Use provisions or have otherwise gone legally unmolested, implying (albeit potentially falsely) a de facto legal validity.
The Japanese culture is generally permissive with regard to the appropriation of ideas. Works such as doujinshi, unauthorized comics continuing the story of an official comic series, are actually encouraged by many anime makers. These doujinshi take an original copyrighted work and expand upon the story, allowing the characters to continue on after, before, or during the original story. Most anime makers encourage this practice, as it expands their series. Some see it as a tribute, others see it from a business viewpoint, that it draws in more support for the anime than it would have had otherwise.
Comiket, a convention that occurs twice a year in Tokyo, manages to pull in a crowd of 350,000 fans and artists, most of whom buy, sell, and trade doujinshi. Lessig has stated, "This market exists in parallel to the mainstream commercial manga market." Furthermore, cosplay (costume-play) conventions persist across Japan. These are conventions in which people will dress up in homemade costumes made to match specific characters; this practice is not discouraged or prosecuted in any way under Japanese copyright or trademark law. Many notable anime and manga authors will attend both of these types of conventions themselves, and convention participants have historically taken this as a sign of the authors' approval. In a similar sense, several original anime cartoonists have flown to various places in the U.S. to attend AMV conventions, especially the larger ones such as AtlantaCon. Many of these animators have also expressed approval of the making of AMVs.
The question has been raised of how such works can continue to exist, or such organizations to flourish, when they do so in legally muddy waters. The answer is that many of the Japanese authors encourage it - several of these authors began their careers with the same kinds of projects they witness anime fans working on today (ex. CLAMP).
By contrast, many U.S. vendors who have acquired anime series or motion pictures have expressed disapproval of AMV works made with those series or motion pictures and have insisted said videos be withdrawn from distribution. In recent years, some of these companies have begun to demand that AMVs made with their content be removed from sites like YouTube, Google Video, or the Animemusicvideos.org AMV aggregation site.
Certain musical performers, as well as their representative record labels, have been requesting the removal of some music videos from websites where they are made available for download. Public opinion and rumors give varying accounts of exactly how widespread these actions have become. Several months ago, the administrator of Animemusicvideos.org was contacted by Wind-Up Records, requesting the removal of content featuring the work of the bands Evanescence, Creed, and Seether. This action generated tremendous ill will toward the record company among many fans of the band and AMVs alike, and since then rumors have claimed the label threatened to shut the site down. The site administrator has stored archival copies of the exchange between the label and the site's staff and published them on the site for public review.
With regard to legality, as has been stated before, AMVs exist in a grey area that encompasses a wide range of current copyright-related matters. Where video content is concerned, most anime makers approve of the fanmade works and many have officially stated their approval of the practice. Where music is concerned, the videos themselves aren't a problem, but their distribution is.