How Many Songs Does it Hold?

This varies greatly based on what size the songs are and whate other things you have on the iPhone.
if you want rough averages then we'll say an average song is about 3Mb
Now on my 8Gb iPhone i have about 7.08free after the Firmware and everything is taken into account so
7,080MB's roughly speaking depending if your talking in Decimal or Binary
now you still won't be able to use all this as some will be taken up with "other" files so we'll just round it off to 6,000MB to be on the side of caution
that would allow for roughly about 2,000 songs (though Apple puts it down as about 1,750) But all this is fluid depending on the size of your music files and the like.
All up it comes out to say 145-166 hours or 8,750-10,000mins of music (assuming about an average of 5mins per song)or about 6-7days worth of music
you can work out the 16GB model the same way but it'll be roughly just over double the storage.

NOTE:
Once again as i said these figures are definitely rough as so much depends on music size, length, and other things including size of the firmware and so many other factors.
So to sum up don't take this as gospel

This depends on the size of each song in your iTunes library that you want to transfer. Was all the music in your iTunes library purchased from the iTunes store? Have you purchased any iTunes plus songs which is encoded at a higher bit rate and takes up more space? If some of your music was imported into your iTunes library from a music CD, what did you use for the encoding with the import? Using MP3 for the encoding uses a little more storage space than AAC for the same song.

Apple's XXX amount of songs that each iPod and iPhone can hold is based on one megabyte for each minute of music - a regular AAC encoded song that is 4 minutes in length is roughly 4MB in size.

Copied from this link about the iPod Touch, which will be similar to the iPhone for the 8GB and 16GB.

http://store.apple.com/us/browse/home/shopipod/family/ipodtouch?mco=MTIxMTE

+Music capacity is based on 4 minutes per song and 128-Kbps AAC encoding.+

Up to 1750 songs for the 8GB, and up to 3500 songs for the 16GB with no other data such as video and/or photos transferred from your computer to the iPhone.

I currently have "only" 670 songs available on my iPhone which takes up 2.91GB of storage space. If I listened to each song once straight through without stopping, it would take me nearly a full two days or nearly 48 hours to listen to each song once.