How to use LINQ to select into an object?

songs.UserSongs.GroupBy(x => x.User).Select(g => new SongsForUser() 
{ 
    User = g.Key,
    Songs = g.Select(s => s.SongId).ToList()
});

I suspect you want:

var songsByUser = songs.UserSongs
                       .GroupBy(song => song.UserId, song => song.SongId)
                       .Select(g => new SongsForUser { User = g.Key,
                                                       Songs = g.ToList() });

To explain, after the GroupBy you'll have a bunch of groups, where the key of each group is the user ID, and the values within the group are the song IDs:

Key = 1, Values = 1, 4, 12
Key = 2, Value = 95

Then you're just converting that into your SongsForUser type. Note that you don't need to explicitly include the () when calling the constructor in an object initializer - it's implicit unless you need to specify constructor arguments.

You could do this all in one GroupBy call, by the way:

var songsByUser = songs.UserSongs
         .GroupBy(song => song.UserId, song => song.SongId,
                  (user, ids) => new SongsForUser { User = user,
                                                    Songs = ids.ToList() });

Personally I usually find a separate Select call to be more readable.

You can also do all of this with a query expression:

var songsByUser = from song in songs.UserSongs
                  group song.SongId by song.UserId into g
                  select new SongsForUser { User = g.Key, Songs = g.ToList() };

EDIT: The above is "provider-neutral" but it sounds like it's not working with LINQ to Entities. You may be able to get it to work like this:

var songsByUser = songs.UserSongs
                       .GroupBy(song => song.UserId, song => song.SongId)
                       .AsEnumerable()
                       .Select(g => new SongsForUser { User = g.Key,
                                                       Songs = g.ToList() });

The AsEnumerable call will force the grouping to be done in the database, but the final projection (including the ToList call) to be done locally. You should check the generated SQL for efficiency though.