Entity FrameWork Many to Many relationship using Asp.Net

First if you have many-to-many relation between Song and Album your Song entity should contain collection of Albums and the Album entity should contain collection of Songs:

public class Song
{
    ...
    public virtual ICollection<Album> Albums { get; set; }
}

public class Album
{
    ...
    public virtual ICollection<Song> Songs { get; set; }
}

Don't forget to map them. For example if you use Fluent API add this to your context class:

protected override void OnModelCreating(DbModelBuilder modelBuilder)
        {
            base.OnModelCreating(modelBuilder);

            modelBuilder.Entity<Song>()
                .HasMany(s => s.Albums)
                .WithMany(a => a.Songs)
                .Map(m =>
                {
                    m.MapLeftKey("SongID");
                    m.MapRightKey("AlbumID");
                    m.ToTable("SongAlbums");
                });
        }

So your method will be similar to this one:

public int CreateNewSong(String name, String songTitle, String album)
{
    using(var context = new Myentities())
    {
        Album album = context.Albums.Single(o => o.AlbumName == album);
        Artist refer = context.Artists.Single(o => o.ArtistName == name);
        Song theNewSong = new Song {
                                      SongTitle = songTitle,
                                      Artist = refer                                        
                                   };

        theNewSong.Albums.Add(album);     
        context.Songs.AddObject(theNewSong);
        context.SaveChanges();
        return theNewSong.SongID;
    }
}

I think this happens because you have a 1 to many relationship between song and album so you have to define which album is associated with the song (as you put artist)

public int CreateNewSong(String name,String songTitle,String album)
{
    using(var context = new Myentities())
    {
        Song theNewSong = new Song()
        Artist refer = context.Artists.Single(o => o.ArtistName == name);

        Album album = context.Albums.Single(o => o.AlbumName == album);

        theNewSong.SongTitle = songTitle;

        theNewSong.Artist_ArtistID = refer.ArtistID;
        theNewSong.Album_AlbumID = album.AlbumID;
        context.Songs.AddObject(theNewSong);
        context.SaveChanges();
        return theNewSong.SongID;
    }
}

I think this may work

Very good answer algreat, let my highlight 2 points because I've been stucked with an error of EF Many - to - Many relantionship (the corresponding navigation property was sending and exception and not retrieving the information) and it's important:

• The Mapping in the OnCreatingModel, if you don't map to the corresponding intermediate table, EF cannot find this object to perform the join, is the table that's omitted in the edmx file.

• If you are using the tools for generate the entities and the data context, wich is my case, and modify the edmx file you'll probably have to code this again because all this "generated objects" will refresh to the initial state and your mapping, your data annotations and that stuff will be erased.

Hope this helps!