If you are planning on using the standard rectangular 9V battery, it will have enough energy for about 1/4 of a charge, and you will waste nearly half of that in the regulator.
Bob
http://en.wikipedia.org/wiki/Nine-volt_battery#Technical_specifications
Will show you the capacity of different 9V battery chemistries.
It's common to have at least 2000mAh in a phone battery. (mine is a 2600mAh)
Your regulator will bring the voltage down to 5V... but the same current that flows into the phone will flow from the battery. They will not give you much of a charge.
Another way to look at it is...
9V x 1.2Ah (Lithium) = 10.8W stored in the battery.
(remember that the same current flows through the entire regulator... so)
5V x 1.2Ah (Result to phone) = 6W stored in the phone.
4V x 1.2Ah (regulator losses) = 4.8W lost as heat.
A little under half of the 'power' in the battery is lost in the regulator as BobK mentioned.
It will work, but is inefficient, and you will need to splurge on high end 9V batteries to give you any decent charge...