You're on the right track with point 2, but you should probably check out some database design articles before trying to program the system... In fact, a very similar example to your problem is dealt with in the introduction of the O'Reilly MySQL book...
Anyway, you'll probably want two tables, one for albums, and one for songs, something like:
album
albumId (Primary Key)
albumTitle
albumArtist
song
songId (Primary Key)
albumId (Foreign Key)
songName
songUrl
If you wanted to design the db properly (which you'll want to do after getting to grips with some database design, e.g. normalisation), you'd probably take 'artist' out of the album table and create an 'artist' table, with an id and name field, which you could then link from a foreign key in either the album or song table. I say 'album OR song', because if you have a compilation album, then you may want to record the artist for each individual song, rather than just specifying a single artist for the album.
If you get the chance, I'd definitely take a look at the O'Reilly book - there's a good intro to database design, and a little on integrating MySQL with PHP.
Don't worry about the size of the database - MySQL can handle millions of rows of data, and 600 songs or so will not use much disk space at all.
Hope this helps.
