It depends on the length and encoding used for the song.
For a 128kbps bit rate song, it is approximately 1 MB per minute. For a 256kbps bit rate song its approximately 2MB per minute. Leave a little overhead for things like album artwork, ID3 tags, and some things to do with how drives store data (block size for one), that is about 100 minutes or 500 minutes per gigabyte. iTunes DRM protected songs are encoded at 128kbps bit rate. iTunes Plus songs are encoded at 256kbps bit rate. Most songs are about 4 minutes on average. If we use that as an average we are looking at about 125-250 songs per gigabyte.
The iPhone and iPod touch do have some space reserved for system software as well. Figure roughly 7GB of storage is available. That would be 775-1750 songs per 8 GB iPhone with 4 minute songs.
Hope this helps,
Nathan C.