Where are the battery graphs?

Unity Users:

When you click on the indicator, and you see the time left on your battery, click that menu item. It should open a window that allows you to see this info:

KDE Users:

You can find this info under "Energy Information" in Kinfocenter. Note that you won't find any graphs on a system that is plugged in.

GNOME Users:

Simply run gnome-power-statistics in a terminal

or open the Power Statistics app from the GNOME Shell

Since you asked for this:

I could get it to show me interesting graphs of the battery state, and how it had changed over time.

1. Go to the Laptop battery option
2. Select the History tab
3. Uncheck Show data points at the bottom if you want

And you will get a graph like this:

While I haven't seen the behavior that you're talking about (I've been using Ubuntu since 10.04, so it hasn't been that long), I do know that you can install a battery graphing package. Instructions below:

1. Install battery-stats from the software center .

2. Run battery-graph by hitting Alt-F2 and typing battery-graph

There you go! Example screenshot shown below: