User stories are used in some Agile methodologies, but are not necessarily an "Agile" notion.
Stories are measured in "story points". A "story point" is the unit.
Story points measure relative complexity of a story. If one story is 2 points and another is 4 points, the latter is believed to be twice as complex/time consuming as the former.
If you do iterative development, you should be able to get a grip on how much you can complete in an iteration. If you take the ratio of story points associated with what you complete and the duration of the iteration, you have what is called project velocity: story points/iteration
Take a look at Mike Cohn's User Stories Applied for the most complete explanation of how this all works.