There are a few issues here.
The datasheet on Sparkfun's site is for a different regulator than the one they're actually selling and shipping to people.
Batteries are a pain in the butt
The regulator sparkfun sells is the ST L7805C, not the old LM7805 stalwart we know and love. The L7805C is an extra crappy (but cheap!) clone of the LM7805. By clone, I mean it does the same thing and has similar specs, but it isn't the same part just made by a different company. It's a independantly designed part. Here is the actual datasheet for the part you're using. The critical differences are as follows:
The L7805C requires a minimum load of 5mA for the output to be in regulation. The quiescent current does NOT count towards that number. It also has a maximum output current of 500mA, not 1 or 1.5A. It thirdly has a thermal resistance of 50°C/W, the numbers in the other answer for power dissipation are nonsense. If you have an ambient of 50°C, you have 100°C of temperature headroom. 2W will cause this part to heat up 100°C above ambient. Any more than that, and you'll need to lower it's thermal resistance to ambient with a heatsink or copper pour.
The L7805C has a typical dropout of 2V. A typical rating in a datasheet does not, in anyway, imply a guarantee of any sort. If the dropout is typically 2V, that means its probably around that, but it might be higher, it might be lower. The part that is a guarantee is the 'max' and 'min' values in a datasheet. The L7805C has none for drop out. That means that this part is not specced or checked to make sure the dropout is within any maximum value. The L7805/L7805A (no letter implies A), which is the better version, has a maximum drop out of 2.5V. Considering that is the GOOD version, and the 7805C doesn't even spec a maximum drop out... all I can say is, do you like do gamble?
This part can put out have a nominal output voltage of 4.75 and 5.25V. Nominal. That means other factors can influence that number further. It's load regulation is only guaranteed to be 100mV. That means higher loads could cause, say, a 4.8V nominal output to fall to 4.7V. Worse, dropout is defined as a 5% fall in nominal output voltage, so if a regulator has a higher than normal drop out of 2.5V (which definitely happens), then if you're inputting 7.2V (2.5V above 4.7V) then the 4.7V may only be 4.46V. Personally, I would not call that 5V, but ST apparently does. It says so in the datasheet.
Most of the specs are specified with an input of 10V. It's also sold by large distributors like Farnell etc. as a 10V minimum input regulator. Sure, it will probably "work" (as long as your definition of "work" is as loose as the datasheet's) with just 8V in, or even 7V. Probably. If it doesn't, the datasheet never promised it would. If you want to be sure, you'd buy the L7805A version with it's maximum dropout of 2.5V (or better yet, buy the TI part), but that's not what Sparkfun is selling.
The L7805 is literally the cheapest and crappiest 5V regulator 20¢ can buy. And you definitely get 20¢ worth of regulator. Er, it costs 19¢ each for a whole real of 2500. Even one costs 45¢ from a distributor. Unless that distributor is Sparkfun. It would appear they think anything with '7805' in the name is equivalent, and bought a ton of the cheapest part available, because that's exactly what they're selling, only using TI's LM7805 datasheet. I don't think there is any foul play here, I think someone at Sparkfun simply doesn't know that the L7805 and LM7805 are different parts.
Now, about batteries. For primary cells (non-rechargeable batteries), the voltage is their peak voltage. This is the voltage they will putout if fresh and basically full. Alkaline cells start at 1.5V, but this voltage falls as they are discharged, until it reaches 0.9-0.8V. A 9V is 6 of these cells in series. Considering the heavy (for a 9V battery) load of as much as 8mA quiescent current on top of 5mA output current, a high quality 9V battery from Energizer will spend nearly 40% of its capacity at a terminal voltage that is less than 7V.
So no, this regulator is not going to meet your expectations if you plan to use an alkaline 9V battery.
Secondary cell battery voltages on the other hand refer to the AVERAGE voltage. An NiMH cell has an average voltage of 1.2V, but have very flat discharge curves, and will actually run things longer and put out a higher voltage than alkaline cells for much longer, despite the common myth that rechargeables are not as high power or otherwise less potent than alkaline cells. If one labeled primary cells using average voltage like rechargeable cells, alkaline batteries would be 1.1V cells. Rechargeable NiMH cells are objectively superior to alkaline cells in every measurable way, except for self-discharge. They're fairly terrible in that metric, but only that one.
A typical "9V" NiMH battery will have 7 1.2V NiMH cells in series for 8.4V average. By the end of their useful life, they'll still not fall below 1V, so you'll always have at least 7V. They also have much lower internal resistance, so loading will not be an issue if the load is just a microcontroller. NiCds are more or less the same in terms of voltage levels and discharge curves as well, but have very poor capacity compared to NiMH. There are also some nice LiIon 9V cells out there which, unfortunately, will start at 8.4V but will fall below 7V before their capacity is used up. But there will be a more reasonable 20% or so left when this happens, so they're better than alkaline cells. They also have great capacity. Personally, I prefer LiIon 9Vs to any other chemistry.
So yes, if you use a NiMH or NiCd 8.4V rechargeable "9V" battery, an LM7805 will meet your expectations. The regulator Sparkfun is selling is NOT an LM7805, but an L7805C.
A L7805C will probably meet your expectations, but it also might not. It's a gamble that the specs of the specific part you receive will be good enough, and the datasheet makes it clear that some of these parts can be quite terrible and be 'in spec'. It's a gamble.
