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.
On my 8GB iPhone, I have fit as many as 1400 songs. These were all songs purchased on iTunes so most were 128 kbps and a few hundred were 256 iTunes plus.
I haven't seen how many I can fit on my 16GB yet, I barely have 1319 songs so far that I have loaded.
I went back and returned by 8gb to the 16gb, luckily I had a few days left on my 14 day rtn policy and that went really smooth, paid my 10% restocking fee and out in 8 minutes. But anyway, I have now exactly 3700 songs on my 16gb phone and have 2.05gb left, I have a few pictures on the phone but not many, maybe 10 or so.